Dynamic DR-Submodular Maximization with Linear Costs over the Integer Lattice

Submodular maximization is to maximize a submodular function under specific constraints, which plays a crucial role in both theoretical combinatorial optimization and practical machine learning. Submodular functions are defined as a class of set functions that exhibit the property of diminishing returns. The domain of submodular functions can be extended from sets to the integer lattice, with numerous ongoing studies. This paper focuses on designing dynamic algorithms for the problem of maximizing a non-negative monotone DR-submodular function f minus a non-negative linear cost function c, both defined over the integer lattice. Under a box constraint, our dynamic algorithm achieves a \((\frac{1}{2}, 1)\) -approximation ratio with amortized time complexity of \(O(\frac{r^{*}\vert \vert \boldsymbol{b}\vert \vert _1\log \vert \vert \boldsymbol{b}\vert \vert _1\log \vert \vert \boldsymbol{b}\vert \vert _\infty }{\epsilon ^{2}})\) , where the amortized time refers to the number of oracle queries of f per update. Significantly, our dynamic algorithms are capable of handling the scenarios where multiple identical elements are simultaneously inserted or deleted at each time. This paper provides a comprehensive framework that extends beyond traditional set-based approaches, offering insights into the behavior and performance of dynamic algorithms in the context of multisets.