收录:
摘要:
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.
关键词:
通讯作者信息:
电子邮件地址: