Indexed by:
Abstract:
In this paper, we study the generalized submodular maximization problem with a nonnegative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter alpha is an element of [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 alpha = 1. For general value of the curvature parameter alpha is an element of [0, 1], we present an approximation algorithm with a factor of 1+h(alpha)(y)+Delta.[3+alpha-(2+alpha)y-(1+alpha)h(alpha)(y)]/2+alpha+(1+alpha)(1-y), where y is an element of [0, 1] is a predefined parameter for tuning the ratio. In particular, when alpha = 1 we obtain a ratio 0.5008 when setting y = 0.9, coinciding with the renowned state-of-art approximate ratio; when alpha = 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. (C) 2021 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
INTERNATIONAL JOURNAL OF CARDIOLOGY
ISSN: 0167-5273
Year: 2021
Volume: 343
4 . 0 3 9
JCR@2021
3 . 2 0 0
JCR@2023
ESI Discipline: CLINICAL MEDICINE;
ESI HC Threshold:90
JCR Journal Grade:2
CAS Journal Grade:3
Cited Count:
SCOPUS Cited Count: 5
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: