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.
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.