Tight lower bounds for the asymmetric k-center problem
Eran Halperin, Technion and Cornell University
February 13, 2004

Abstract

In the Asymmetric k-Center problem, the input is an integer k and a
complete graph over n points together with a distance function
obeying the directed triangle inequality. The goal is to choose a set of
k points to serve as centers, so that the maximum distance from the
centers to any point is as small as possible.

We show that the Asymmetric k-Center problem is hard to approximate up to
a factor of log^* n - Theta(1) unless every problem in NP can be solved in
quasi-polynomial time. Since an O(log^* n)-approximation algorithm is
known for the problem, this essentially resolves the approximability of
this problem.

Joint work with J. Chuzhoy, S. Guha, S. Khanna, G. Kortsarz and J. Naor.