Fully Dynamic Unconstrained Submodular Maximization

arXiv:2610.38865 · cs.DS · Submitted 2026-10-28 · Read on arXiv

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