mapreduce
-
Submodular Optimization in the MapReduce ModelPaul Liu and Jan Vondrák
[pdf]
Submodular optimization has received significant attention in both practice and theory, as a wide array of problems in machine learning, auction theory, and combinatorial optimization have submodular structure. In practice, these problems often involve large amounts of data, and must be solved in a distributed way. One popular framework for running such distributed algorithms is MapReduce. In this paper, we present two simple algorithms for cardinality constrained submodular optimization in the MapReduce model: the first is a $(1/2 - o(1))$-approximation in 2 MapReduce rounds, and the second is a $(1 - 1/e - \epsilon)$-approximation in $\frac{1+o(1)}{\epsilon}$ MapReduce rounds.
-
Greedy and Local Ratio Algorithms in the MapReduce ModelNicholas J. A. Harvey, Christopher Liaw, Paul Liu
[pdf] [slides]
MapReduce has become the de facto standard model for designing distributed algorithms to process big data on a cluster. There has been considerable research on designing efficient MapReduce algorithms for clustering, graph optimization, and submodular optimization problems. We develop new techniques for designing greedy and local ratio algorithms in this setting. Our randomized local ratio technique gives 2-approximations for weighted vertex cover and weighted matching, and an $f$-approximation for weighted set cover, all in a constant number of MapReduce rounds. Our randomized greedy technique gives algorithms for maximal independent set, maximal clique, and a $(1+\epsilon)\log \Delta$-approximation for weighted set cover. We also give greedy algorithms for vertex colouring with $(1+o(1))\Delta$ colours and edge colouring with $(1+o(1))\Delta$ colours.