Greedy and Local Ratio Algorithms in the MapReduce Model

06/17/2018
by   Nicholas J. A. Harvey, et al.
0

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+ϵ)Δ-approximation for weighted set cover. We also give greedy algorithms for vertex colouring with (1+o(1))Δ colours and edge colouring with (1+o(1))Δ colours.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset