Integer Programming and Combinatorial Optimization

Given a set V of n points and the distances between each pair, the k-center problem asks us to choose a subset C ⊆ 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.