cs.DSNov 15, 2026

Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse

Authors: Vaneet Aggarwal

Organizations: Purdue University, West Lafayette, IN 47907, USA

Abstract

We study the maximization of a nonnegative submodular function under a cardinality constraint when elements arrive one at a time and an algorithm must report a feasible set after every arrival. The recourse of an algorithm is the largest number of insertions and deletions that it makes to the reported set at a single arrival. For every ε>0ε>0, we give an algorithm with recourse O(ε−2)O(ε^{-2}) whose reported set has, at every time, expected value at least 1/4−ε1/4-ε times the largest value of a feasible set of arrived elements. The algorithm evaluates the function polynomially often, and only on sets of arrived elements. We also show that no algorithm with constant recourse achieves a ratio above 1/41/4, even if it knows the function and the arrival order in advance and has unlimited computation, and that any fixed ratio above 1/41/4 requires recourse that grows as a positive power of the cardinality budget. Thus 1/41/4 is the optimal limiting ratio with constant recourse. The previous best ratio with constant recourse was 3−22≈0.1723-2\sqrt2\approx0.172. Our algorithm assigns selection probabilities of at most one half and maintains, as elements arrive, an inequality bounding the value of every feasible set by a multiple of the expected value of a random set drawn with these probabilities; the reported set moves to a rounding of these probabilities through gradual replacements. The upper bound uses a weighted directed graph whose vertices arrive in groups of decreasing sizes.

Figures & tables

Explore similar work

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.
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 8, 2026

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

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.