Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-035 | 21st May 2003 00:00

Tight lower bounds for the asymmetric k-center problem



In the {\sc $k$-center} problem, the input is a bound $k$
and $n$ points with the distance between every two of them,
such that the distances obey the triangle inequality.
The goal is to choose a set of $k$ points to serve as centers,
so that the maximum distance from the centers $C$ to any point
is as small as possible.
This fundamental facility location problem is $\NP$-hard.
The symmetric case is well-understood from the viewpoint of approximation;
it admits a $2$--approximation,
but not better.

We address the approximability of the asymmetric $k$-center problem.
Our first result shows that the linear program used by [Archer, 2001]
to devise $O(\log^* k)$--approximation
has integrality ratio that is at least $(1-o(1))\log^* n$;
this improves on the previous bound $3$ of [Archer, 2001].
Using a similar construction, we then prove that the problem cannot
be approximated within a ratio of $\frac{1}{4}\log^*n$,
unless $NP\subseteq DTIME(n^{\log\log\log n})$.
These are the first lower bounds for this problem that are tight,
up to constant factors,
with the $O(\log^* n)$--approximation due to [Panigrahy and Vishwanathan, 1998] and [Archer, 2001].

ISSN 1433-8092 | Imprint