Deterministic approximation algorithm for submodular maximization subject to a matroid constraint

In this paper, we study the generalized submodular maximization problem with a non-negative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter α ∈ [ 0, 1 ] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for α = 1. For general value of the curvature parameter α ∈ [ 0, 1 ], we present an approximation algorithm with a factor of 1 + h α ( y ) + Δ ⋅ [ 3 + α − ( 2 + α ) y − ( 1 + α ) h α ( y ) ] 2 + α + ( 1 + α ) ( 1 − y ), where y ∈ [ 0, 1 ] is a predefined parameter for tuning the ratio. In particular, when α = 1 we obtain a ratio 0. 5008 when setting y = 0. 9, coinciding with the renowned state-of-art approximate ratio; when α = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions.

Authors

• Xin Sun Harbin Institute of Technology
• Dachuan Xu Beijing University of Technology, Beijing, China
• Longkun Guo College of Computer and Data Science, Fuzhou University Shandong Fundamental Research Center for Computer Science
• Min Li School of Computer Science and Engineering, Central South University, China

Keywords

• Approximation algorithm
• Submodular maximization
• Total curvature
• Matroid constraint
• Deterministic algorithm