Indexed by:
Abstract:
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 [Formula presented], 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. © 2021 Elsevier B.V.
Keyword:
Reprint 's Address:
Email:
Source :
Theoretical Computer Science
ISSN: 0304-3975
Year: 2021
Volume: 890
Page: 1-15
1 . 0 0 2
JCR@2021
0 . 9 0 0
JCR@2023
ESI HC Threshold:106
JCR Journal Grade:4
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count: 5
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 2
Affiliated Colleges: