Paper Info
Title
Constrained non-monotone submodular maximization: offline and secretary algorithms
Abstract
Constrained submodular maximization problems have long been studied, most recently in the context of auctions and computational advertising, with near-optimal results known under a variety of constraints when the submodular function is monotone. In this paper, we give constant approximation algorithms for the non-monotone case that work for p-independence systems (which generalize constraints given by the intersection of p matroids that had been studied previously), where the running time is poly(n, p). Our algorithms and analyses are simple, and essentially reduce non-monotone maximization to multiple runs of the greedy algorithm previously used in the monotone case. We extend these ideas to give a simple greedy-based constant factor algorithms for non-monotone submodular maximization subject to a knapsack constraint, and for (online) secretary setting (where elements arrive one at a time in random order and the algorithm must make irrevocable decisions) subject to uniform matroid or a partition matroid constraint. Finally, we give an O(log k) approximation in the secretary setting subject to a general matroid constraint of rank k.
Year
DOI
Venue
2010
10.1007/978-3-642-17572-5_20
Clinical Orthopaedics and Related Research
Keywords
DocType
Volume
submodular function,secretary algorithm,submodular maximization problem,non-monotone submodular maximization subject,partition matroid constraint,constant approximation algorithm,knapsack constraint,non-monotone case,general matroid constraint,uniform matroid,non-monotone maximization,polynomial time,local search,greedy algorithm,monotone function,game theory,data structure
Conference
abs/1003.1517
ISSN
ISBN
Citations 
0302-9743
3-642-17571-6
43
PageRank 
References 
Authors
1.92
24
4
Name
Order
Citations
PageRank
Anupam Gupta12989210.44
Aaron Roth21937110.48
Grant Schoenebeck350939.48
Kunal Talwar44423259.79