Fully Dynamic Submodular Maximization over a Matroid with Polylogarithmic Update Time

We study fully dynamic maximization of a normalized monotone submodular function subject to a matroid constraint of rank at most $k$. For every oblivious sequence of $n$ insertions and deletions and $0<ϵ\le 1/10$, our randomized algorithm maintains a feasible set $X_t$ satisfying $\mathbb{E}[f(X_t)]\ge (1/4-ϵ){\mathrm{OPT}}_t$ at every fixed time $t$. The total number of value- and independence-oracle queries is $O\left(\frac{n}{ϵ}{\log }^3(k/ϵ)\log (2k){\log }^2(2n)\right)$ for every realization of the random choices, giving polylogarithmic amortized query complexity for fixed $ϵ$. Our approach combines a deletion-tolerant exchange certificate with deterministic hierarchical rebuilding. The certificate charges the optimum to the frozen weights of retained and deleted acceptances. Exact truncated sampling controls expected deletion loss and leaves small residuals for later rebuilding levels, yielding the approximation and query guarantees.