CS Paper Radar

Consistent Submodular Maximization with Full Foresight

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

cs.DS cs.LG ·submitted 2026-11-04 09:32 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS cs.LGmath.OC ·2026-11-08 ·Vaneet Aggarwal
similarity 0.75
Abstract

Elements arrive one at a time, and after each arrival an algorithm holds a set of at most $k$ arrived elements. Its goal is a held set whose value under a monotone submodular function is close to the best value that $k$ 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 $k$ and of the number $n$ 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-\sqrt{2}\approx0.5858$. We show that seeing future arrivals raises the best ratio for polynomially many evaluations to $1-1/e\approx0.6321$, for deterministic and for randomized algorithms; no algorithm with polynomially many evaluations exceeds $1-1/e$, even when all elements are available at once. For every $\varepsilon>0$, a deterministic algorithm that sees the next $\lceil\varepsilon k/3\rceil$ arrivals keeps a set of value at least $1-1/e-\varepsilon$ times the optimum at every time, changes $O(\varepsilon^{-3})$ elements per arrival and makes $(n+1)^{O(\varepsilon^{-2})}$ evaluations. With the whole arrival sequence known in advance, a deterministic algorithm attains the same ratio with $O(\varepsilon^{-2})$ changes per arrival. A randomized algorithm with the same short lookahead makes $O(n^2k)$ evaluations, changes $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.

0.16

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

cs.DS cs.LG ·2026-11-15 ·Vaneet Aggarwal
theory similarity 0.74
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$, we give an algorithm with recourse $O(ε^{-2})$ whose reported set has, at every time, expected value at least $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/4$, even if it knows the function and the arrival order in advance and has unlimited computation, and that any fixed ratio above $1/4$ requires recourse that grows as a positive power of the cardinality budget. Thus $1/4$ is the optimal limiting ratio with constant recourse. The previous best ratio with constant recourse was $3-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.

0.12

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

cs.DS cs.LG ·2026-09-09 ·Shi Fu, Qixin Zhang, Dacheng Tao
theory similarity 0.71
Abstract

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.

0.45

Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness

cs.DS ·2026-09-18 ·Anish Hebbar, Ravi Kumar, Roie Levin, Joseph, Naor +1 more
similarity 0.65
Abstract

Suppose an online algorithm is given an unbiased $p$-sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance? We study this online algorithms with a sample (OAS) model. We show a tight $O\left(\log (1/p) \cdot \log m + \log n\right)$-competitive algorithm for set cover, exponentially improving upon the $O\left(1/p \cdot \log (mn)\right)$ guarantee of Gupta et al. (SODA'24) and answering an open question therein. Our techniques extend to covering integer programs and non-metric facility location, also yielding tight bounds for these problems. Further, we give an $O(\log (1/p)/ \log \log (1/p))$-competitive algorithm for metric facility location, answering an open question of Argue et al. (NeurIPS'22). We then introduce and study the robust variant of the OAS model, in which an adversary is allowed to arbitrarily modify $k$ elements of the $p$-sample. For set cover, covering integer programs, and non-metric facility location, we obtain a tight competitive ratio of $O\left(\log (k/p) \cdot \log m + \log n\right)$. For metric facility location and Steiner tree, we obtain tight competitive ratios of $O\left(\log (k/p) / \log \log (k/p) \right)$ and $O\left(\log (k/p)\right)$ respectively. To the best of our knowledge, these are the first results for robust algorithms in the OAS setting.

0.19

On the Computational Complexity of Problems: Formalizing Sensitivity to Uncertainty and Parametric Complexity Classes

cs.CC ·2026-10-04 ·Yannis Tzitzikas
theory similarity 0.64
Abstract · 40 pages

Worst-case analysis, the setting of the $P \stackrel{?}{=} NP$ question, measures the cost of a problem as a function of input size alone. Yet problems that are exponential in general often become polynomial, even linear, once a checkable property of the input is known: Partition, for instance, is decidable in linear time on inputs whose elements are all equal. We develop a framework that makes such knowledge an explicit parameter $K$ of complexity statements. Costs are measured for fixed algorithms; we distinguish the promise cost from the guarded cost that also pays for checking $K$, and introduce the residual uncertainty $Ψ(n,K)$, the number of input cells that, together with $K$, determine the input. An Uncertainty Reduction Theorem decomposes the guarded cost into checking $K$, locating and reading the residual information, and solving an explicit reduced problem. The classes $P_\upsilon[K]$ and $NP_\upsilon[K]$ are restrictions to polynomial-time promises, made informative by the coverage of $K$. We show that small $Ψ$ forces sparsity but not tractability, characterize FPT as uniform membership in graded families $P_\upsilon[K_k]$, prove a free-variable threshold for SAT, and show that under the factoring assumption no checkable property of non-negligible coverage makes factoring easy. We relate the framework to promise problems, kernelization, average- and generic-case complexity and beyond-worst-case analysis, illustrate it on Partition, Graph Isomorphism, SAT, Vertex Cover and TSP, and apply it to guarded algorithm dispatch with latency contracts and optimal guard ordering, to solver routing in agentic AI, and to the role of promises in quantum speedups.

0.34

Safety Hacking in Constrained Best-of-$N$ Inference-time Scaling

cs.LG cs.AIcs.CLcs.CR ·2026-08-24 ·Akifumi Wachi, Takumi Tanabe, Youhei Akimoto
similarity 0.64
Abstract

Inference-time pipelines often sample multiple outputs, filter them with a learned safety model, and return the proxy-feasible output with the highest learned reward. We show that this composition creates a two-stage failure: an imperfect safety proxy first contaminates the feasible set with unsafe outputs, and reward maximization can then amplify this residual contamination. We define \emph{safety hacking} as selecting an output that passes the learned constraint but violates the true safety criterion. For constrained Best-of-$N$ sampling, we derive finite-$N$ bounds governed by the joint upper reward tails of safe and unsafe outputs within the proxy-feasible set. If unsafe-but-feasible outputs have the heavier tail, safety hacking becomes asymptotically certain as $N$ grows, even when false-positive mass and average safety- and reward-proxy errors are arbitrarily small. We also show that policies within a bounded $χ^2$ divergence from the proxy-feasible reference distribution admit an $N$-independent safety-hacking bound, and instantiate this general coverage-control principle with constrained pessimistic sampling. Coverage control limits amplification but cannot repair a contaminated feasible set: admitted unsafe outputs may still be favored, and regularized selection is not necessarily safer than constrained Best-of-$N$ for every reward proxy. Toy and language-model experiments characterize both contamination and its reward-tail amplification, which exposes an inherent difficulty in inference-time scaling with learned safety models.

0.37

Minimization Prophet Inequality with Bounded Costs

cs.DS ·2026-09-06 ·Haolong Li, Xiaowei Wu
similarity 0.64
Abstract

We study the cost-minimization prophet inequality problem, in which a decision-maker sequentially observes $n$ independent and identically distributed (IID) random variables. After each observation, the decision-maker must either accept the current realization and stop, or reject it and continue with the next variable. The goal is to minimize the selected value. Unlike the classical maximization setting, if none of the first $n-1$ values is accepted, the final realization must be selected. Esfandiari et al. (SIDMA 2017) showed that this problem does not admit constant-competitive online algorithms in general, which motivates subsequent work on restricted distribution classes, such as entire distributions (Livanos and Mehta, SODA 2024) and distributions with bounded extreme values (Livanos and Mehta, EC 2025). In this work, we focus on distributions with bounded support. For distributions supported on $[1,b]$, we characterize the competitive ratio of online algorithms as a function of both $b$ and $n$. We consider both distribution-aware and distribution-oblivious settings. In the distribution-aware case, we provide a nearly tight characterization of the optimal online algorithm, showing that its competitive ratio is at most $b^{(1-1/n)^n}$ for all $n\geq 2$. More significantly, we design a distribution-oblivious algorithm that achieves the same guarantee, with a sequence of predetermined thresholds that depend only on $b$ and $n$. Furthermore, we extend our analysis to the non-IID setting, where we show that a simple single-threshold algorithm attains an asymptotically optimal competitive ratio of $Θ(\sqrt{b})$.

0.27

Fully Dynamic Unconstrained Submodular Maximization

cs.DS ·2026-10-28 ·Mohammad Hajiaghayi
theory similarity 0.63
Abstract

We study unconstrained maximization of a fixed nonnegative submodular function when the ground set changes by insertions and deletions. A uniformly random subset gives a $1/4$-approximation with constantly many value-oracle queries per update. We obtain improvements over this bound for arbitrary oblivious update sequences, without knowing future deletions. For value estimation, we give a $(\sqrt2-1-\varepsilon)$-approximation using $O_{\varepsilon,δ}(\log^2(N+1))$ expected amortized oracle queries, with failure probability at most $δ$ at each fixed time. Here $N$ bounds the number of active elements. The algorithm maintains Poisson samples of the positive mass of random chain lower bounds. We prove that the factor $\sqrt2-1$ is tight for this certificate, even when polynomially many independent orders are used. For every fixed integer $K\ge2$, we maintain a feasible $(1/4+Ω(K^{-2}))$-approximate set using $\widetilde O_K(N^{1/K})$ amortized queries. Thus every fixed exponent $γ>0$ permits a fixed improvement over $1/4$ with $\widetilde O_γ(N^γ)$ update queries. In the square-root regime, a stronger algorithm attains $ρ_{\rm sq}-\varepsilon$, where $ρ_{\rm sq}>0.3177$. The maintained sets are feasible after every update, and their approximation guarantees hold in expectation. All bounds count oracle queries; the value estimator may query previously seen inactive elements, whereas the set algorithms use only currently active elements.

0.07