Consistent Submodular Maximization with Full Foresight

Consistent submodular maximization aims to maintain a high-utility subset of size at most $k$ as new elements arrive one by one, while changing only a limited number of elements per update. Previously, [DFL+25](STOC '25) established an information-theoretic bound of $2/3$ and gave the first polynomial-time randomized algorithm with a $0.51$-approximation guarantee. However, a fundamental question remained open: Is it possible to design an efficient algorithm for consistent submodular maximization that matches the classical offline $(1-1/e)$-approximation? In this paper, we answer this question in the negative by proving that the sharp approximation threshold achievable with polynomially many value queries and worst-case constant recourse is $$β:=2-\sqrt{2}\approx0.5858<1-1/e.$$ Specifically, we develop an improved poly-time randomized algorithm, which can attain a $(β-\varepsilon)$-approximation in expectation at each fixed time with $O(\varepsilon^{-2})$ worst-case recourse. The cornerstone of this algorithm is a novel anchored sampling scheme, which uses only value queries on subsets of the elements seen so far to construct a solution that remains competitive under unknown future arrivals. Conversely, we establish a matching lower bound by showing that any fixed improvement over $β$ requires either exponentially many value queries or $Ω(k)$ changes per update. Furthermore, we characterize the impact of curvature by establishing a sharp threshold of $1-(\sqrt{2}-1)\vartheta$ for consistent submodular maximization, where $\vartheta\in[0,1]$ denotes the total curvature. Surprisingly, for weighted coverage objectives, we devise a poly-time randomized algorithm that can match the optimal $(1-1/e-\varepsilon)$-approximation with $O(\varepsilon^{-1})$ worst-case recourse, thereby separating coverage maximization from general submodular maximization in the consistent settings.

Consistency is an important property in dynamic submodular maximization and entails maintaining a near-optimal solution at all times, making only a small number of adjustments to the solution in each step. Prior work has explored this question for the insertion-only case, where the algorithm faces a stream of $n$ insertions, and has established lower and upper bounds for the cardinality-constrained version of the problem. We consider this question in the fully dynamic setting, where the stream of operations may contain both insertions and deletions. We develop a general framework for designing algorithms for this setting, and instantiate it to obtain the first constant-factor approximations with sublinear consistency. For cardinality constraints, we propose a $\frac 12 - O(\varepsilon)$ approximation that is $O\left(\frac{1}{\varepsilon^2}\right)$ consistent. For rank-$k$ matroid constraints, we construct a $\frac 14 - O(\varepsilon)$ approximation to the dynamic optimum that is $O\left(\frac{\log k}{\varepsilon^2}\right)$ consistent.

We study nonnegative submodular maximization on $n$ elements subject to a general matroid of rank $k$, when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors $1/e$ for non-monotone objectives and $1-1/e$ for monotone objectives. More precisely, given an error bound $ξ\ge0$, under every controlled oracle $\widehat f$ satisfying $|\widehat f(S)-f(S)|\le ξ$ for every set $S$, our implementation returns a feasible set with expected value at least $(1/e-\varepsilon)OPT-O(kξ)$ and $(1-1/e-\varepsilon)OPT-O(kξ)$, respectively, where $OPT$ is the feasible optimum. The implementation uses a deterministically bounded budget of $O(nk^{2}\varepsilon^{-2}\log n\log^{2}(1/\varepsilon))$ oracle calls. As a consequence, an offline-to-online reduction yields full-bandit combinatorial multi-armed bandit (CMAB) algorithms for general matroid-constrained submodular rewards with exact limiting approximation-regret factors $1/e$ and $1-1/e$ and $\widetilde O(n^{1/5}k^{4/5}T^{4/5})$ regret over $T$ rounds. These online guarantees allow exploration to play sets that become independent after deleting at most one element; exploitation and the benchmark remain matroid-feasible. For unit-capacity partition matroids we obtain $\widetilde O(n^{1/5}k^{3/5}T^{4/5})$ under the same exploration relaxation. We establish a deterministic query budget by truncating the Poisson process and identify the enlarged action set needed to answer its offline queries.