Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-038 | 15th May 2003 00:00

Asymmetric k-center is log^*n-hard to Approximate

RSS-Feed




TR03-038
Authors: Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor
Publication: 4th June 2003 18:31
Downloads: 1527
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint