Search papers, labs, and topics across Lattice.
Resolving an open question on consistent submodular maximization under dynamic arrivals with bounded recourse, this paper determines the exact tractability threshold for maintaining stable near-optimal subsets. The authors prove that the supremum approximation ratio achievable with polynomial value queries and worst-case $O(1)$ recourse is precisely $\beta = 2 - \sqrt{2} \approx 0.5858$, strictly below the offline $1 - 1/e$ bound. Surpassing this barrier is fundamentally impossible without sacrificing stability or efficiency, as any improvement requires either exponential queries or linear $\Omega(k)$ recourse per insertion.
Online submodular optimization cannot match the classic $1-1/e$ guarantee under stable updates: beating $2-\sqrt{2} \approx 0.5858$ provably triggers either an exponential query explosion or catastrophic $\Omega(k)$ recourse per step.
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\"utting 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 \[ \beta=2-\sqrt2\approx0.5858<1-1/e. \] For every $\varepsilon>0$, our randomized algorithm attains $\beta-\varepsilon$ with $O(\varepsilon^{-2})$ changes per insertion. Any fixed improvement requires exponentially many queries before one critical insertion or linear recourse of $\Omega(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.
