Summary: Given a set \(V\) of \(n\) points and the distances between each pair, the \(k\)-center problem asks us to choose a subset \(C\subseteq V\) of size \(k\) that minimizes the maximum over all points of the distance from \(C\) to the point. This problem is NP-hard even when the distances are symmetric and satisfy the triangle inequality, and Hochbaum and Shmoys gave a best-possible 2-approximation for this case. We consider the version where the distances are asymmetric. Panigrahy and Vishwanathan gave an \(O(\log^*n)\)-approximation for this case, leading many to believe that a constant approximation factor should be possible. Their approach is purely combinatorial. We show how to use a natural linear programming relaxation to define a promising new measure of progress, and use it to obtain two different \(O(\log^*k)\)-approximation algorithms. There is hope of obtaining further improvement from this LP, since we do not know of an instance where it has an integrality gap worse than 3.
For the entire collection see [Zbl 0967.00091].