This work proposes a framework for the general knapsack-constrained submodular maximization problems that incorporates advice from learning models or domain experts and is ρ-robust and 1-consistent, where ρ is the provable worst-case guarantee.
Abstract
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.
Maximizing a submodular function subject to a matroid constraint is a cornerstone problem in combinatorial optimization. The state-of-the-art algorithm for this problem obtains $0.401$-approximation~\cite{buchbinder2024constrained}, and the state-of-the-art hardness result shows that no polynomial time algorithm can ob...
A matroid extended greedy algorithm is proposed for the k-submodular cover problem, its bi-criteria approximation ratio is analyzed, and an improved approximation ratio under the special case of unit costs is derived.
Xin-Rui Li, Dong-Lei Du, Qian Liu et al.· 0 citations
We consider the problem of approximately maximizing a weakly submodular function using the standard greedy algorithm, which is known to give tight approximation results for such functions under a cardinality constraint. We show that this is not the case for general matroid constraints. For any $\gamma<1$, we give a fam...
The multi-armed bandit problem models the trade-off between exploration and exploitation. In this paper, we study the variant where exploration has a hard budget and precedes exploitation. Prior guarantees include a 1/3 approximation by Guha and Munagala using Lagrangian duality, and a 4/27 approximation by Ma against...
We revisit the online submodular welfare maximization problem (OSW), a vast generalization of numerous well-studied online allocation problems, including online bipartite matching, display ads and AdWords. A natural greedy OSW algorithm achieves a competitive ratio of $1/2$ [LLN06], and $1-1/e$ under i.i.d. arrivals [K...