Consistent Submodular Maximization with Full Foresight

Eric Balkanski; Paul Dütting; Federico Fusco; Silvio Lattanzi; Ashkan Norouzi-Fard; Ola Svensson; Morteza Zadimoghaddam

cs.DSNov 4, 2026

Consistent Submodular Maximization with Full Foresight

Authors: Eric Balkanski, Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, Morteza Zadimoghaddam

Organizations: Columbia University · Google Research · Sapienza University of Rome · EPFL

Abstract

Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. We ask a fundamental question that separates consistency from the other two: what does solution stability cost when the entire future is known and computation is unlimited? We answer this question for monotone submodular maximization, where an algorithm must maintain a solution of at most $k$ arrived elements, with a constant number of changes per step. We determine the optimal approximation thresholds: $3/4$ for deterministic algorithms and $ξ^\star \approx 0.7942$ for randomized algorithms. For every $\varepsilon>0$ , we get within $\varepsilon$ of these thresholds with worst-case recourse polynomial in $1/\varepsilon$ , independent of $k$ and the stream length. We prove matching impossibility results even for coverage functions. We attain the sharp bounds by optimally balancing two opposing forces: preparing for future arrivals and protecting the current solution. For randomized algorithms, we use addition robustness against prefixes of the known future, which we analyze tightly via an interval-selection problem. For deterministic algorithms, we introduce certificates, paths in a fractional relaxation that maintain high value, which we round into an update schedule.

Figures & tables

Figure 1: Overview of results. A single value is a tight threshold; an interval gives the best known lower and upper bounds. Poly time refers to algorithms that make polynomially many value queries and run in polynomial time, and info-theoretic to algorithms with unrestricted computation. The upper bound of

1-1/e

in polynomial time holds even without consistency constraints ( Nemhauser and Wolsey, 1978 ; Feige, 1998 ) .

Panel of Figure 2 — Figure 2: The hard coverage instance for the randomized lower bound.

Panel of Figure 3 — Figure 3: Proof roadmap for the randomized algorithm.

Panel of Figure 4 — Figure 4: Interval representation of the hard coverage instance in Figure 2 , with values normalized by $k$ . The future prefixes $\varnothing$ , $\{U_{0}\}$ , and $\{U_{0},U_{1}\}$ give the intervals $I_{0}=[0,1]$ , $I_{1}=[1,1+u_{1}]$ , and $I_{2}=[1+u_{1},1+u_{1}+u_{2}]$ , respectively. Their lengths $1,u_{1},u_{2}$ are the normalized gains from selecting all $k$ singleton sets in the first, second, and third groups, respectively.

Panel of Figure 5 — Figure 5: Left: Consistency forces the row fraction $\alpha_{t}$ to pass within $\varepsilon$ of $\nicefrac{{1}}{{2}}$ at some step $t^{*}$ . Right: The idealized halfway state, with $\nicefrac{{k}}{{2}}$ rows and $\nicefrac{{k}}{{2}}$ columns, covers $\nicefrac{{3}}{{4}}$ of $U_{\text{core}}$ and $\nicefrac{{1}}{{2}}$ of $U_{\text{aux}}$ , while the complete stage $B_{j}$ covers both completely.

Panel of Figure 6 — Figure 6: A clairvoyant certificate ( Definition 3.1 ) in the simplex $\Delta$ of mixtures; the top vertex stands for the intermediate candidates. The anchor $p$ is persistent, the entry path from $\delta_{0}$ is safe at stage $0$ , the exit path to $\delta_{m}$ is safe at stage $m$ , and the number of segments governs the consistency.

Panel of Figure 7 — Figure 7: The schedule of the reduction. Blocks of $\Theta(\varepsilon k)$ arrivals are divided into $\lceil\nicefrac{{4}}{{\varepsilon}}\rceil$ subintervals of $\Theta(\varepsilon^{2}k)$ arrivals. In each block, the transition (red) takes place in the first subinterval during which the optimum grows by at most a factor of $1+\varepsilon$ ; subintervals in which it grows faster (orange) are skipped. A window runs from one transition to the next; in between, the core holds the rounded anchor of the window, and during a transition, the algorithm performs $O(\nicefrac{{L}}{{\varepsilon^{2}}})$ changes per arrival.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 8 — Figure 8: Construction of the hard instance for deterministic consistent algorithms.

Online Submodular Optimization

See all 8 papers

A Sharp Barrier of Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse
Sep 9, 2026Shi Fu, Qixin Zhang, Dacheng TaoSubmodular Optimization Query Complexity
Nanyang Technological University, Singapore
A General Framework for Dynamic Consistent Submodular Maximization
Jun 3, 2026Paul Dütting, Federico Fusco, Silvio Lattanzi +3Submodular Optimization Approximation Algorithms
1Google Research · 2Dept. of Computer, Control and Management Engineering, Sapienza University of Rome · 3EPFL
Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning
Aug 12, 2026Vaneet AggarwalSubmodular Optimization Combinatorial Multi-Armed Bandits
V. Aggarwal is with Purdue University, West Lafayette IN, USA

Sep 9, 2026J/K move · Enter open · S save

A Sharp Barrier of Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse

Shi Fu, Qixin Zhang, Dacheng Tao

Nanyang Technological University, Singapore

Submodular Optimization Query Complexity Approximation Algorithms

Open paper AskPDF arXiv

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.

Abstract

Online Submodular Optimization

Explore similar work

A Sharp Barrier of Consistent Submodular Maximization: Any Improvement over 2−22-\sqrt{2}2−2​ Entails Exponential Queries or Linear Recourse

A General Framework for Dynamic Consistent Submodular Maximization

Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning

A Sharp Barrier of Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse