A New Framework for Distributed Submodular Maximization

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distributed algorithms for these problems. However, these results suffer from high number of rounds, suboptimal approximation ratios, or both. We develop a framework for bringing existing algorithms in the sequential setting to the distributed setting, achieving near optimal approximation ratios for many settings in only a constant number of MapReduce rounds. Our techniques also give a fast sequential algorithm for non-monotone maximization subject to a matroid constraint.


Published in:
2016 Ieee 57Th Annual Symposium On Foundations Of Computer Science (Focs), 645-654
Presented at:
57th IEEE Annual Symposium on Foundations of Computer Science (FOCS), New Brunswick, NJ, OCT 09-11, 2016
Year:
2016
Publisher:
New York, Ieee
ISSN:
0272-5428
ISBN:
978-1-5090-3933-3
Laboratories:




 Record created 2017-02-17, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)