Skip to content

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

Sep 2026 · ACM SIGMETRICS Performance Evaluation Review · Vol 54, pp. 65 - 67 · 0 citations · 9 references

TL;DR

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.

View source

Similar papers

Preprint Oct 2026

Stronger Hardness for Submodular Maximization Subject to a Matroid Constraint

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...

Moran Feldman, A. Kuhnle · 2 citations
Preprint Oct 2026

k-Submodular Cover Problem with a Matroid Constraint

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
Preprint Sep 2026

On Maximizing a Weakly Submodular Function over a Matroid Constraint via the Greedy Algorithm

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...

Justin Ward, Moran Feldman · 1 citation
Preprint Oct 2026

Budgeted Bayesian Bandits for Future Utilization

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...

Sudipto Guha · 0 citations
Preprint Oct 2026

Online Submodular Welfare Maximization: Computation is not the Bottleneck

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...

Rajan Udwani, David Wajc · 3 citations · ⚡2

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.