Fast Greedy Algorithms in MapReduce and Streaming
Citations Over TimeTop 1% of 2015 papers
Abstract
Greedy algorithms are practitioners’ best friends—they are intuitive, are 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. Armed with this primitive, we then adapt a broad class of greedy algorithms to the MapReduce paradigm; this class includes maximum cover and submodular maximization subject to p -system constraint problems. 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.
Related Papers
- Greedy algorithm for the solution of the question of 0/1 knapsack(2006)
- → Generalizations of Matroids(2011)
- → Generalizations of Matroids(2007)
- → Generalizations of Matroids(2002)
- → Entropic Weighted Rank Function(2022)