Non-monotone submodular function maximization under k-system constraint

Majun Shi, Zishen Yang, Donghyun Kim and Wei Wang ()
Additional contact information
Majun Shi: Xi’an Jiaotong University
Zishen Yang: Xi’an Jiaotong University
Donghyun Kim: Georgia State University
Wei Wang: Xi’an Jiaotong University

Journal of Combinatorial Optimization, 2021, vol. 41, issue 1, No 10, 128-142

Abstract: Abstract The problems of maximizing constrained monotone submodular functions have many practical applications, most recently in the context of combinatorial optimization, operations research, economics and especially machine learning, with constant approximation algorithms known under a variety of constraints. Unfortunately, non-monotone submodular functions maximization is less well studied; the first approximation algorithm for the non-monotone case was studied by Feige et al. (Proceedings of the 48th IEEE symposium on foundations of computer science (FOCS’07), 2007) about unconstrained non-monotone submodular maximization in 2007. In this paper, we extend the work of Lee et al. (Proceedings of the 41st ACM-SIAM symposium on theory of computing (STOC’09), pp 323–332, 2009) for maximizing a non-monotone submodular function under k-matroid constraint to k-system constraint. We first propose a Modified-Greedy algorithm that works no worse than that of Gupta et al. (Proceedings of the 6th international workshop on internet and network economics (WINE’10), vol 6484, pp 246–257, 2010). Based on this, then we provide the NMSFMk algorithm for maximizing a non-monotone submodular function subject to k-system constraint (which generalizes the k-matroid constraint), using Modified-Greedy algorithm combined with USFM algorithm (USFM algorithm is the random linear time 1/2-approximation algorithm proposed by Buchbinder et al. (Proceedings of the 53rd IEEE symposium on foundations of computer science (FOCS’12), pp 649–658, 2012) for unconstrained non-monotone submodular function maximization problem.) iteratively. Finally, we show that NMSFMk algorithm achieves a $$\frac{1}{2k+3+1/k}$$ 1 2 k + 3 + 1 / k -approximation ratio with running time of O(nmk) (where m is the size of largest set returned by the NMSFMk algorithm), which beats the existing algorithms in many aspects.

Keywords: Submodular maximization; k-system; Modified-Greedy algorithm; NMSFMk algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00672-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:1:d:10.1007_s10878-020-00672-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00672-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().