Non-monotone submodular function maximization under k -system constraint
- PDF / 306,635 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 100 Downloads / 184 Views
Non-monotone submodular function maximization under k-system constraint Majun Shi1 · Zishen Yang1 · Donghyun Kim2 · Wei Wang1 Accepted: 5 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 ModifiedGreedy 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 1 problem.) iteratively. Finally, we show that NMSFMk algorithm achieves a 2k+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
Supported by National Natural Science Foundation of China under Grant No. 11971376. Extended author information available on the last page of the article
123
Journal of Combinatorial Optimization
1 Introduction Submodular function optimization is ubiquitous in diverse areas and recently a growing number of problems can be expressed as submodular function maximization. Let V = {1, 2, · · · , n} be a ground set. The set function f : 2V → R is called submodular if for every S, T ⊆ V , f (S) + f (T ) ≥ f (S ∪ T ) + f (S ∩ T ). Submodular function has a diminishing returns property: f (S ∪ {i}) − f (S) ≥ f (T ∪ {i}) − f (T ) for any S ⊆ T ⊆ V \{i} (see Fujishige 2005 for more about submodular function). This property occurs naturally in many applications in combinatorial optimization, operations research, machine learning, economics and so on. In this paper, we consider the problem
Data Loading...
