Parallel Approximation Algorithms for Metric Facility Location
Oct 27, 2010
Given a set of facilities and their costs, a set of clients, and a distance metric, which facilities should be opened to minimize the total cost---the combined facility cost and the sum of the distances from each client to the closest opened facility? This problem is known as the metric facility location problem, which is NP-hard, but several approximation algorithms have been given for the sequential case.
In this talk, I will discuss how to parallelize a simple greedy approximation algorithm of Jain, Mahdian, Markakis, Saberi, Vazirani (JACM'03). Here, the major challenge is to overcome the inherent sequential nature of the greedy algorithm while preserving the solution's quality. At the heart of our techniques is a combinatorial problem, a generalization of maximal independent set, which turns out to be useful in parallelizing other greedy algorithms as well.
This is joint work with Guy Blelloch.