Dynamic algorithms for maximizing a DR-submodular function subtracted by a linear function over the integer lattice

Submodular maximization plays a fundamental role in combinatorial optimization. Recently, driven by real-world applications, there has been growing interest in studying submodularity over the integer lattice. In this paper, we propose dynamic algorithms for two distinct problems. First, for maximizing a monotone DR-submodular function minus a linear function over a bounded integer lattice c = ( c 1, c 2, ⋯, c n ) ∈ Z + n, we develop a ( 1 2, 1 ) -bicriteria approximation algorithm, with an amortized update query complexity of O ( r ^ | | c | | 1 log | | c | | 1 log | | c | | ∞ ϵ 2 ), where r ^ represents the average number of elements inserted or deleted per update, and the amortized update time corresponds to the amortized number of oracle queries per update. Second, we extend this problem to include an additional cardinality constraint k, and propose a different dynamic algorithm that achieves a ( 3 − 5 2, 1 ) -bicriteria approximation with an amortized update query complexity of O ( r ^ k log | | c | | 1 log | | c | | ∞ ϵ 2 ). Unlike classical dynamic models, our framework allows for the simultaneous insertions or deletions of multiple identical elements. This paper presents a unified approach that extends beyond conventional set-based methods, offering new perspectives on the efficiency and behavior of dynamic algorithms in a multiset setting.

Authors

• Yuanyuan Qiang
• Bin Liu

Keywords

• Submodular functions
• Integer lattice
• Dynamic algorithms
• Approximation algorithms