TCS Journal 2024 Journal Article
A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity
- Shengminjie Chen
- Donglei Du
- Ruiqi Yang
- Wenguo Yang
- Yapu Zhang
In this work, we investigate the problem of maximizing nonmonotone DR-submodular function (possibly negative) subject to cardinality constraints on an integer lattice space. We propose a M-Threshold Decrease Algorithm that uses a compensation constant M from a special decomposition h ( x ) = f ( x ) − g ( x ), which achieves a 1 − e − δ − ϵ approximation guarantee. To ensure that the algorithm ends in finite time, the supremum of δ is δ ( ϵ ) = ϵ max s ∈ Ω h ( χ s | 0 ) 2 k max s ∈ Ω g ( χ s | 0 ) + ϵ max s ∈ Ω h ( χ s | 0 ). If max s ∈ Ω h ( χ s | 0 ) > 2 k max s ∈ Ω g ( χ s | 0 ), there exists ϵ ⁎ = arg max ϵ ∈ ( 0, 1 ) 1 − e − δ ( ϵ ) − ϵ such that 1 − e − δ ( ϵ ⁎ ) − ϵ ⁎ > 0. This implies that there is a valid δ such that 1 − e − δ − ϵ > 0. To accelerate the algorithm, we employ a random subset to replace the ground set and propose a Random M-Threshold Decrease Algorithm, where δ ( ϵ ) = ϵ r max s ∈ Ω h ( χ s | 0 ) 2 n k max s ∈ Ω g ( χ s | 0 ) + [ k ( n − r ) + ϵ r ] max s ∈ Ω h ( χ s | 0 ) with r being the size of the random subset and n being the size of the ground set. Furthermore, we demonstrate that, based on the DR-ratio γ d and the DS decomposition, the M-Threshold Decrease Algorithm is also suitable for solving the monotone non-DR-submodular maximization problem, achieving a 1 − e − γ d δ − O ( ϵ ) approximation guarantee. Because γ d is a challenging metric to calculate, we refine the M-Threshold Decrease Algorithm, which can return an estimate of γ d. To the best of our knowledge, this is the first time that a single factor approximation ratio has been proposed for the nonmonotone DR-submodular maximization problem (possibly negative) subject to cardinality constraints.