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

Back to Seminar Series schedule page