# Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse

DevFeed: [Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse](<https://devfeed.tech/articles/tight-bounds-for-non-monotone-submodular-maximization-under-a-cardinality-constraint-with-constant-recourse-139013.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.20257>)

Author: Vaneet Aggarwal

Published: 2026-11-17T05:00:00Z

Content type: news

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [2](<https://devfeed.tech/tags/2.md>), [3](<https://devfeed.tech/tags/3.md>), [abstract](<https://devfeed.tech/tags/abstract.md>), [after](<https://devfeed.tech/tags/after.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [also](<https://devfeed.tech/tags/also.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [best](<https://devfeed.tech/tags/best.md>), [budget](<https://devfeed.tech/tags/budget.md>), [cardinality](<https://devfeed.tech/tags/cardinality.md>), [constraint](<https://devfeed.tech/tags/constraint.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [elements](<https://devfeed.tech/tags/elements.md>), [fixed](<https://devfeed.tech/tags/fixed.md>), [function](<https://devfeed.tech/tags/function.md>), [graph](<https://devfeed.tech/tags/graph.md>), [groups](<https://devfeed.tech/tags/groups.md>), [half](<https://devfeed.tech/tags/half.md>), [inequality](<https://devfeed.tech/tags/inequality.md>), [under](<https://devfeed.tech/tags/under.md>), [with](<https://devfeed.tech/tags/with.md>)

## AI overview

For online maximization of a nonnegative, non-monotone submodular function under a cardinality constraint, the paper gives an algorithm with recourse O(ε⁻²) and expected value at least (1/4−ε) times the best feasible set of arrived elements at every step. It makes polynomially many function evaluations, only on sets of arrived elements. The authors prove 1/4 is the optimal limiting ratio for constant recourse, even with advance knowledge of the function and arrival order and unlimited computation; any fixed ratio above 1/4 requires recourse growing as a positive power of the cardinality budget. The method caps selection probabilities at one half, maintains a bound relating feasible-set values to the expected value of a random set, and gradually replaces elements to round those probabilities. The excerpt reports an improvement over the previous constant-recourse ratio of about 0.172.

## Source excerpt

arXiv:2611.20257v1 Announce Type: cross 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 $\epsilon>0$, we give an algorithm with recourse $O(\epsilon^{-2})$ whose reported set has, at every time, expected value at least $1/4-\epsilon$ 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 $1/4$, even if it knows the function and the arrival order in advance and has unlimited computation, and that any fixed ratio above $1/4$ requires recourse that grows as a positive power of the cardinality budget. Thus $1/4$ is the optimal limiting ratio with constant recourse. The previous best ratio with constant recourse was $3-2\sqrt2\approx0.172$. 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.