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

Yuanyuan Qiang

doi:10.1016/j.tcs.2026.115877

Return

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

2026-05-12

PRE

Yuanyuan Qiang

Bin Liu *

DOI：10.1016/j.tcs.2026.115877

Original

Original request for help

Save

Abstract

En 中文

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 = = (c1, c2, ... , cn) is an element of & Zopf;n+, we develop a ( 12,1)-bicriteria approximation algorithm, with an amortized update query complexity of O(f log II=II1log II=II infinity), where r represents epsilon 2 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 root that achieves a ( 3-2 , 1)-bicriteria approximation with an amortized update query complexity of 5 O(Pklog II=II1 log II=II infinity ). Unlike classical dynamic models, our framework allows for the simultaneous epsilon 2 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.

Keywords:

Submodular functions

Integer lattice

Dynamic algorithms

Approximation algorithms