Indexed by:
Abstract:
We study the problem of maximizing non-monotone submodular functions subject to a p-independence system constraint. Although the submodularity ratio has been well-studied in maximizing set functions under monotonic scenario, the defined parameter may bring hardness of approximation for the maximization of set functions in the non-monotonic case. In this work, utilizing a lower bound for the marginal values, we investigate the Repeated Greedy introduced by (Feldman et al. 2017) and obtain a parameterized performance guarantee for the above constrained submodular maximization problem. © 2021, Springer Nature Switzerland AG.
Keyword:
Reprint Author's Address:
Email:
Source :
ISSN: 0302-9743
Year: 2021
Volume: 12606 LNCS
Page: 353-361
Language: English
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 3
Affiliated Colleges: