Indexed by:
Abstract:
In this paper, we consider the problem of maximizing a non-submodular set function subject to a matroid constraint with the continuous generic submodularity ratio γ. It quantifies how close a monotone function is to being submodular. As our main contribution, we propose a (1-e-γ2-O(Ε)) -approximation algorithm when the submodularity ratio is sufficiently large. Our work also can be seen as the first extension of the adaptive sequencing technique in non-submodular case. © 2020, Springer Nature Switzerland AG.
Keyword:
Reprint Author's Address:
Email:
Source :
ISSN: 0302-9743
Year: 2020
Volume: 12575 LNCS
Page: 3-13
Language: English
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 3
Affiliated Colleges: