ECCC-Report TR03-035https://eccc.weizmann.ac.il/report/2003/035Comments and Revisions published for TR03-035en-usWed, 28 May 2003 17:46:58 +0300
Paper TR03-035
| Tight lower bounds for the asymmetric k-center problem |
Eran Halperin,
Guy Kortsarz,
Robert Krauthgamer
https://eccc.weizmann.ac.il/report/2003/035In 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].
Wed, 28 May 2003 17:46:58 +0300https://eccc.weizmann.ac.il/report/2003/035