Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/FOCS.2016.74 | 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | Field | DocType |
Distributed submodular maximization,MapReduce,approximation algorithms | Matroid,Mathematical optimization,Submodular set function,Document summarization,Submodular maximization,Theoretical computer science,Distributed algorithm,Cluster analysis,Sequential algorithm,Mathematics,Maximization | Journal |
Volume | ISSN | ISBN |
abs/1507.03719 | 0272-5428 | 978-1-5090-3934-0 |
Citations | PageRank | References |
13 | 0.90 | 21 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rafael da Ponte Barbosa | 1 | 35 | 1.78 |
| Alina Ene | 2 | 409 | 25.47 |
| Huy L. Nguyen | 3 | 376 | 32.33 |
| Justin Ward | 4 | 101 | 7.33 |