TR03-038 Authors: Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor

Publication: 4th June 2003 18:31

Downloads: 3304

Keywords:

We show that the asymmetric $k$-center problem is

$\Omega(\log^* n)$-hard to approximate unless

${\rm NP} \subseteq {\rm DTIME}(n^{poly(\log \log n)})$.

Since an $O(\log^* n)$-approximation algorithm is known

for this problem, this essentially resolves the approximability

of this problem. This is the first natural problem

whose approximability threshold does not polynomially relate

to the known approximation classes.

Our techniques also resolve the approximability threshold of

the weighted metric $k$-center problem. We show that it

is hard to approximate to within a factor of

$3 - \epsilon$ for any $\epsilon > 0$.