A Learning-Augmented Framework for Knapsack-Constrained Submodular Maximization Problems

Many machine learning tasks involve maximizing a submodular function with constraints. However, constrained submodular maximization problems are known to be NP-hard. Although there exist efficient approximation algorithms, approximation guarantees cannot be improved without auxiliary information, unless P = NP. In this work, we propose a framework for the general knapsack-constrained submodular maximization problems that incorporates advice from learning models or domain experts. Our framework is flexible and can use various existing offline ρ-approximation algorithms as subroutines. For both monotone and non-monotone cases, we prove that when the advice is arbitrarily bad, our framework produces solutions with guarantees no worse than the subroutine algorithms (without advice); when the advice is optimal, the framework is optimal. In other words, the proposed framework is ρ-robust and 1-consistent, where ρ is the provable worst-case guarantee.