Name
Abstract | ||
|---|---|---|
Greedy algorithms are practitioners' best friends - they are intuitive, simple to implement, and often lead to very good solutions. However, implementing greedy algorithms in a distributed setting is challenging since the greedy choice is inherently sequential, and it is not clear how to take advantage of the extra processing power. Our main result is a powerful sampling technique that aids in parallelization of sequential algorithms. We then show how to use this primitive to adapt a broad class of greedy algorithms to the MapReduce paradigm; this class includes maximum cover and submodular maximization subject to p-system constraints. Our method yields efficient algorithms that run in a logarithmic number of rounds, while obtaining solutions that are arbitrarily close to those produced by the standard sequential greedy algorithm. We begin with algorithms for modular maximization subject to a matroid constraint, and then extend this approach to obtain approximation algorithms for submodular maximization subject to knapsack or p-system constraints. Finally, we empirically validate our algorithms, and show that they achieve the same quality of the solution as standard greedy algorithms but run in a substantially fewer number of rounds. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2809814 | parallel computing |
Keywords | Field | DocType |
greedy algorithm,submodular maximization subject,greedy choice,standard greedy algorithm,standard sequential greedy algorithm,modular maximization subject,sequential algorithm,broad class,fewer number,logarithmic number | Maximum coverage problem,Matroid,Approximation algorithm,Mathematical optimization,Computer science,Submodular set function,Greedy algorithm,Theoretical computer science,Knapsack problem,Greedy randomized adaptive search procedure,Maximization | Conference |
Volume | Issue | ISSN |
2 | 3 | 2329-4949 |
Citations | PageRank | References |
20 | 0.85 | 41 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ravi Kumar | 1 | 13932 | 1642.48 |
| Benjamin Moseley | 2 | 554 | 50.11 |
| Sergei Vassilvitskii | 3 | 2750 | 139.31 |
| Andrea Vattani | 4 | 171 | 11.45 |