Fully Dynamic Unconstrained Submodular Maximization
cs.DS
Submitted: 2026-10-28
Updated: 2026-10-28
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study unconstrained maximization of a fixed nonnegative submodular function when the ground set changes by insertions and deletions.
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-epsilon) -approximation using O epsilon,δ(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 at least2, we maintain a feasible (1/4+Ω(K-2)) -approximate set using O K(N 1/K) amortized queries. Thus every fixed exponent γ>0 permits a fixed improvement over 1/4 with O γ(N γ) update queries. In the square-root regime, a stronger algorithm attains ρ sq-epsilon, where ρ 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.
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles