Summary
The paper studies how algorithms can pick good sets of items when those items arrive over time, balancing between getting a high-quality choice and not changing the chosen set too much after each new arrival. The authors prove a sharp limit on how good the choices can be if the algorithm must stay stable and efficient: no efficient method can beat about 58.6% of the best possible offline choice. They also show that trying to improve beyond this limit either needs a huge number of checks or big changes to the chosen set. This helps explain the cost of keeping solutions stable when the future is uncertain.
What this means in practice
- •For online recommendation teams: Design recommendation algorithms that balance good item selection with minimal updates as new data arrives.
- •For supply chain planners: Develop selection methods for inventory or resources that remain stable despite frequent updates, improving operational consistency.
A theory result. No direct application yet.
Abstract
Consistent submodular maximization studies the tradeoff between solution quality and stability when elements arrive over time. For a monotone submodular objective, which models diminishing returns, an algorithm maintains a set of at most $k$ available elements and changes only $O(1)$ elements after each insertion. Dütting et al. [2025] established a tight $2/3$ approximation with unrestricted computation and a polynomial-time $0.51$ approximation. They left open at STOC 2025 whether efficient algorithms can match the offline $1-1/e$ guarantee. We resolve this problem by proving that the supremum approximation achievable with polynomially many value queries and worst-case constant recourse is \[ β=2-\sqrt2\approx0.5858<1-1/e. \] For every $\varepsilon>0$, our randomized algorithm attains $β-\varepsilon$ with $O(\varepsilon^{-2})$ changes per insertion. Any fixed improvement requires exponentially many queries before one critical insertion or linear recourse of $Ω(k)$ changes at that insertion, even with unlimited queries afterwards. This gap quantifies the cost of consistency: the current oracle hides which elements will be needed after an arrival. We also determine the exact curvature-dependent threshold $1-(\sqrt2-1)\vartheta$, attain $1-1/e-\varepsilon$ for weighted coverage with $O(\varepsilon^{-1})$ recourse, and separate the existence of universal future-price certificates from their efficient computation. Our algorithm has a bounded-bit polynomial-time implementation for polynomial-bit rational oracle answers; the lower bound uses only logarithmic-bit rational answers.