Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse
Organizations: Purdue University, West Lafayette, IN 47907, USA
Abstract
We study the maximization of a nonnegative submodular function under a cardinality constraint when elements arrive one at a time and an algorithm must report a feasible set after every arrival. The recourse of an algorithm is the largest number of insertions and deletions that it makes to the reported set at a single arrival. For every , we give an algorithm with recourse whose reported set has, at every time, expected value at least times the largest value of a feasible set of arrived elements. The algorithm evaluates the function polynomially often, and only on sets of arrived elements. We also show that no algorithm with constant recourse achieves a ratio above , even if it knows the function and the arrival order in advance and has unlimited computation, and that any fixed ratio above requires recourse that grows as a positive power of the cardinality budget. Thus is the optimal limiting ratio with constant recourse. The previous best ratio with constant recourse was . Our algorithm assigns selection probabilities of at most one half and maintains, as elements arrive, an inequality bounding the value of every feasible set by a multiple of the expected value of a random set drawn with these probabilities; the reported set moves to a rounding of these probabilities through gradual replacements. The upper bound uses a weighted directed graph whose vertices arrive in groups of decreasing sizes.
Figures & tables
| Setting | Algorithm and queries | Achievable ratio | Upper bound |
|---|---|---|---|
| No limit on recourse | Polynomial queries | Aggarwal and Du (2026) | Aggarwal and Lu (2026) |
| Constant recourse | Polynomial queries on arrived elements | Feldman et al. (2018) Theorem 3 | Theorem 10 , even with full foresight and unrestricted queries |
Submodular Optimization
Submodular optimization studies efficient selection and allocation when each added item tends to provide diminishing returns.
See all 61 papers