arXiv preprint ·
Fully Dynamic Unconstrained Submodular Maximization
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.