The Euclidean k-Supplier Problem

The $k$-supplier problem is a fundamental location problem that involves opening $k$ facilities to minimize the maximum distance of any client to an open facility. We consider the $k$-supplier problem in Euclidean metrics (of arbitrary dimension) and present an algorithm with approximation ratio $1+\sqrt{3}<2.74$. This improves upon the previously known 3-approximation algorithm, which also holds for general metrics. Our result is almost best possible as the Euclidean $k$-supplier problem is NP-hard to approximate better than a factor of $\sqrt{7}>2.64$. We also present a nearly linear time algorithm for the Euclidean $k$-supplier in constant dimensions that achieves an approximation ratio better than three.