cs.DSNov 8, 2026

Optimal Polynomial-Query Approximation for Consistent Submodular Maximization with Short Lookahead

Authors: Vaneet Aggarwal

Organizations: Purdue University

Abstract

Elements arrive one at a time, and after each arrival an algorithm holds a set of at most kk arrived elements. Its goal is a held set whose value under a monotone submodular function is close to the best value that kk arrived elements can achieve. The recourse of an update is the number of elements inserted into or removed from the held set, and we require it to be bounded independently of kk and of the number nn of arrivals. With evaluations only on sets of arrived elements and polynomially many of them, the best ratio a randomized algorithm can achieve is 2−2≈0.58582-\sqrt{2}\approx0.5858. We show that seeing future arrivals raises the best ratio for polynomially many evaluations to 1−1/e≈0.63211-1/e\approx0.6321, for deterministic and for randomized algorithms; no algorithm with polynomially many evaluations exceeds 1−1/e1-1/e, even when all elements are available at once. For every ε>0\varepsilon>0, a deterministic algorithm that sees the next ⌈εk/3⌉\lceil\varepsilon k/3\rceil arrivals keeps a set of value at least 1−1/e−ε1-1/e-\varepsilon times the optimum at every time, changes O(ε−3)O(\varepsilon^{-3}) elements per arrival and makes (n+1)O(ε−2)(n+1)^{O(\varepsilon^{-2})} evaluations. With the whole arrival sequence known in advance, a deterministic algorithm attains the same ratio with O(ε−2)O(\varepsilon^{-2}) changes per arrival. A randomized algorithm with the same short lookahead makes O(n2k)O(n^2k) evaluations, changes O(ε−2)O(\varepsilon^{-2}) elements per arrival, and attains the same ratio in expectation at each fixed time. The main tool is a greedy algorithm with an explicit guarantee for each of its partial solutions combined with each initial segment of the known future arrivals. A second tool moves between two such solutions one element at a time while keeping the value high, and the deterministic algorithm times each move using upper bounds on the optimum from failed searches.

Figures & tables

Explore similar work

Sep 9, 2026

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

Consistent submodular maximization aims to maintain a high-utility subset of size at most kk 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/32/3 and gave the first polynomial-time randomized algorithm with a 0.510.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)(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−2≈0.5858<1−1/e.β:=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(ε−2)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)Ω(k) changes per update. Furthermore, we characterize the impact of curvature by establishing a sharp threshold of 1−(2−1)ϑ1-(\sqrt{2}-1)\vartheta for consistent submodular maximization, where ϑ∈[0,1]\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−ε)(1-1/e-\varepsilon)-approximation with O(ε−1)O(\varepsilon^{-1}) worst-case recourse, thereby separating coverage maximization from general submodular maximization in the consistent settings.
Nov 4, 2026

Consistent Submodular Maximization with Full Foresight

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 kk arrived elements, with a constant number of changes per step. We determine the optimal approximation thresholds: 3/43/4 for deterministic algorithms and ξ⋆≈0.7942ξ^\star \approx 0.7942 for randomized algorithms. For every ε>0\varepsilon>0, we get within ε\varepsilon of these thresholds with worst-case recourse polynomial in 1/ε1/\varepsilon, independent of kk 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.
Jun 3, 2026

A General Framework for Dynamic Consistent Submodular Maximization

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 nn 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 12−O(ε)\frac 12 - O(\varepsilon) approximation that is O(1ε2)O\left(\frac{1}{\varepsilon^2}\right) consistent. For rank-kk matroid constraints, we construct a 14−O(ε)\frac 14 - O(\varepsilon) approximation to the dynamic optimum that is O(log⁡kε2)O\left(\frac{\log k}{\varepsilon^2}\right) consistent.