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

Vaneet AggarwalarXiv 2026 · arXiv

TL;DR

This paper settles a fundamental question in online submodular maximization: how well can we approximate a non-monotone objective if we are only allowed a fixed number of changes to our solution at each step? The author provides a new algorithm achieving a $1/4 - \epsilon$ approximation ratio with constant recourse and proves that $1/4$ is the absolute theoretical limit for any such approach.

What Problem Does This Paper Address?

Submodular functions are the "convex functions" of the discrete world, characterized by the property of diminishing returns: adding an element to a small set helps more than adding it to a larger set. In many real-world scenarios—like maintaining a news summary, a sensor network, or a cache—data arrives one item at a time. We want to maintain a "best" subset of size $k$ at all times.

However, there is a catch: recourse. Changing the selected set (deleting an old item and inserting a new one) often has a high cost. An algorithm has "constant recourse" if the number of changes it makes at each arrival is bounded by a constant that doesn't grow with the size of the data or the budget $k$.

While monotone functions (where more is always better) are well-studied, this paper tackles non-monotone functions, where adding an element might actually decrease the total value (e.g., the "cut" of a graph). Before this paper, the best-known ratio for this problem was $\approx 0.172$.

Methods

The author introduces a framework that combines continuous relaxation with a "lazy" update schedule:

  1. Fractional Solution: Instead of picking items directly, the algorithm maintains a "fractional solution"—a vector of probabilities (capped at $1/2$) for each arrived element.
  2. Checkpoints: The algorithm doesn't recompute everything at every step. Instead, it uses random "checkpoints" to re-evaluate the fractional solution using a local search approach on the multilinear extension of the submodular function.
  3. Gradual Replacement: To keep recourse constant, the algorithm doesn't jump to a new solution immediately. When a checkpoint dictates a new optimal set, the algorithm uses a queue to slowly swap out old elements for new ones over a window of several arrivals.
  4. Randomized Pipage Rounding: This standard technique is used to convert the fractional probabilities into a concrete set while preserving the expected value.

For the hardness proof (the upper bound), the author constructs a "hard instance" using a weighted directed graph where elements arrive in groups of decreasing sizes, forcing any constant-recourse algorithm to "commit" to a suboptimal fraction of early elements.

Datasets

Not discussed in the paper. As a theoretical work, it focuses on mathematical proofs and worst-case analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The 1/4 Barrier: The paper identifies $1/4$ as a "magic number" for non-monotone objectives under recourse. This is a significant improvement over the previous $0.172$ and matches the known bounds for some offline settings.
  • The Power of 1/2: A critical part of the algorithm is ensuring no element has a selection probability higher than $1/2$. This "buffer" allows the algorithm to maintain an inequality that bounds the potential gain of any feasible set, ensuring the expected value stays competitive even if the optimum grows rapidly.
  • Recourse vs. Budget: One of the most striking findings is that if you want to achieve any ratio strictly better than $1/4$, your recourse must grow as a power of the budget $k$. You cannot beat $1/4$ with a constant number of changes.
  • Foresight Doesn't Help: The hardness result holds even if the algorithm has "full foresight"—meaning it knows the entire sequence of arrivals and the function values in advance. The limitation is purely structural due to the recourse constraint.

Key Results

  • Optimal Approximation: The proposed algorithm achieves a ratio of $1/4 - \epsilon$.
  • Constant Recourse: The recourse is $O(\epsilon^{-2})$, which is independent of the budget $k$ and the number of elements $n$.
  • Tight Upper Bound: The paper proves that no constant-recourse algorithm can exceed a $1/4$ ratio.
  • Efficiency: The algorithm uses a polynomial number of value-oracle queries, making it computationally feasible.

Limitations and Future Work

  • Recourse Magnitude: While the recourse is "constant" relative to $k$, the $O(\epsilon^{-2})$ term can become quite large if a very high precision (small $\epsilon$) is required.
  • Query Complexity: While polynomial, the query complexity is $O(N^8)$, which might be too slow for massive-scale streaming applications.
  • Open Questions: The author notes two remaining gaps:
  • What is the absolute smallest recourse (as a function of $\epsilon$) required to hit the $1/4$ mark?
  • What is the minimum number of queries needed to achieve this optimal ratio?

Summary updated

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 $ε>0$, we give an algorithm with recourse $O(ε^{-2})$ whose reported set has, at every time, expected value at least $1/4-ε$ 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.
BibTeX
@misc{aggarwal2026tight,
  author = {Vaneet Aggarwal},
  title = {{Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse}},
  year = {2026},
  eprint = {2611.20257},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.20257},
}
Figure