Fully Dynamic Unconstrained Submodular Maximization
In the authors' words
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 -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 -approximation using expected amortized oracle queries, with failure probability at most at each fixed time. Here 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 is tight for this certificate, even when polynomially many independent orders are used. For every fixed integer , we maintain a feasible -approximate set using amortized queries. Thus every fixed exponent permits a fixed improvement over with update queries. In the square-root regime, a stronger algorithm attains , where . 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.
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.