Fall 2012 Seminar Series

DATE: November 1st
LOCATION: E51-376
TIME: 4:15pm
Reception immediately following

SPEAKER:
Baruch Schieber

TITLE
The Euclidean k-Supplier Problem

ABSTRACT
In the k-supplier problem, we are given a set of clients C and set of facilities F located in a metric, along with a bound $k<= |F|. The goal is to open a subset of k facilities so as to minimize the maximum distance of a client to an open facility. We consider the k-supplier problem in Euclidean metrics and present for it a 1+sqrt{3} ~ 2.73 approximation algorithm. This is an improvement over the 3-approximation algorithm of Hochbaum and Shmoys which also holds for general metrics (where it is known to be tight). By a result of Feder and Greene, it is NP-hard to approximate the Euclidean k-supplier problem to better than a factor of sqrt{7} ~ 2.65, even in 2-dimension. Our algorithm is very simple and is based on a relation to the edge cover problem. We also present a nearly linear time algorithm for Euclidean k-supplier in constant dimensions that achieves an approximation ratio ~2.965. The previously known nearly linear time approximation algorithm in this setting given by Feder and Greene yields a 3-approximation.

 

This is joint work with Viswanath Nagarajan and Hadas Shachnai