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

Shi Fu; Qixin Zhang; Dacheng Tao

cs.DSSep 9, 2026

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

Authors: Shi Fu, Qixin Zhang, Dacheng Tao

Abstract

Consistent submodular maximization studies the tradeoff between solution quality and stability when elements arrive over time. For a monotone submodular objective, which models diminishing returns, an algorithm maintains a set of at most $k$ available elements and changes only $O(1)$ elements after each insertion. Dütting et al. [2025] established a tight $2/3$ approximation with unrestricted computation and a polynomial-time $0.51$ approximation. They left open at STOC 2025 whether efficient algorithms can match the offline $1-1/e$ guarantee. We resolve this problem by proving that the supremum approximation achievable with polynomially many value queries and worst-case constant recourse is

β=2-\sqrt2\approx0.5858<1-1/e.

For every $\varepsilon>0$ , our randomized algorithm attains $β-\varepsilon$ with $O(\varepsilon^{-2})$ changes per insertion. Any fixed improvement requires exponentially many queries before one critical insertion or linear recourse of $Ω(k)$ changes at that insertion, even with unlimited queries afterwards. This gap quantifies the cost of consistency: the current oracle hides which elements will be needed after an arrival. We also determine the exact curvature-dependent threshold $1-(\sqrt2-1)\vartheta$ , attain $1-1/e-\varepsilon$ for weighted coverage with $O(\varepsilon^{-1})$ recourse, and separate the existence of universal future-price certificates from their efficient computation. Our algorithm has a bounded-bit polynomial-time implementation for polynomial-bit rational oracle answers; the lower bound uses only logarithmic-bit rational answers.

Explore similar work

Jun 3, 2026cs.DS

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

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.

Paul Dütting, Federico Fusco, Silvio Lattanzi +3

Submodular Maximization Approximation Algorithms Cardinality Unified Framework

Ask PDF

Jul 7, 2026cs.DS

Data-dependent Evaluations for Budgeted Submodular Maximization

Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is not easy to evaluate how close a produced solution is to an optimal one for a given problem instance. In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint. We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages in certifying how close to optimal a solution is through experiments with real-world datasets.

Lejian Zhang, Xueyan Tang, Jing Tang

Submodular Maximization Knapsack Constraint Approximation Algorithms Upper Bounds Np-Hard

Ask PDF

May 8, 2026cs.LG

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

Submodular functions -- functions exhibiting diminishing returns -- are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves a tight

63\%

approximation. But many practical objectives incorporate costs that make them negative on some inputs, and all existing multiplicative guarantees require non-negativity. Prior work handles negativity through additive bounds for the special class of decomposable functions and non-monotonicity through partial-monotonicity parameters, but these address each difficulty in isolation and neither extends the classical structural theory. We extend \emph{curvature} -- a parameter measuring how far a function deviates from linearity -- to all submodular functions, handling both non-monotonicity and negativity through a single classical concept. A greedy algorithm with pruning achieves a curvature-controlled multiplicative ratio for \emph{any} submodular function, including those taking negative values -- the first such guarantee beyond monotonicity and non-negativity. In the non-monotone regime

1 \le c_g < 2.2

, the bound strictly beats the best known uniform ratio of

0.401

(for non-negative

f

), and it recovers the classical

(1-e^{-c_g})/c_g

guarantee for monotone functions. A multilinear-extension variant extends the framework to general combinatorial constraints via multilinear relaxation. Experiments on cost-penalized experimental design, coverage, feature selection, and a curvature sweep on Multi-News passage selection support the theory.

Yixin Chen, Alan Kuhnle

Submodular Maximization Curvature Monotonicity Curvature-Aware Quadratic Banks Bayesian Experimental Design

Ask PDF