TR03-035 Authors: Eran Halperin, Guy Kortsarz, Robert Krauthgamer

Publication: 28th May 2003 17:46

Downloads: 3212

Keywords:

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].