Algorithms improve dynamic maximization of changing submodular sets
Fully Dynamic Unconstrained Submodular Maximization
Data Structures and Algorithms
Summary
This paper deals with finding the best ways to select items from a changing collection where each addition or removal affects overall value in a complex way. The authors focus on functions called submodular functions, which capture diminishing returns. They develop efficient algorithms that quickly update good selections without knowing future changes and improve over simple random choices. Their methods provide guarantees on how close these selections are to the best possible, even when the set changes unpredictably.
What this means in practice
- •For online advertising teams: Maintain near-optimal dynamic selections of ad subsets as user preferences or inventory change rapidly, improving campaign performance with limited computation.
- •For network resource allocators: Dynamically manage sets of network elements for load balancing or fault tolerance when available resources change over time without knowing future updates.
A theory result. No direct application yet.
Authors
Mohammad Hajiaghayi
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.