← 研踪 PaperTrailarXiv:2610.38865 · v1
Fully Dynamic Unconstrained Submodular Maximization
首次提交 2026-10-29 04:37
版本更新 2026-10-29 04:37
雷达观测 2026-10-30 11:25
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-10-29 04:37 · 最新观测版本
Fully Dynamic Unconstrained Submodular Maximization
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.
查看此版本解读 →查看此版本原文 ↗