ECCC-Report TR03-038https://eccc.weizmann.ac.il/report/2003/038Comments and Revisions published for TR03-038en-usWed, 04 Jun 2003 18:31:18 +0300
Paper TR03-038
| Asymmetric k-center is log^*n-hard to Approximate |
Julia Chuzhoy,
Sudipto Guha,
Sanjeev Khanna,
Seffi Naor
https://eccc.weizmann.ac.il/report/2003/038We 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$.
Wed, 04 Jun 2003 18:31:18 +0300https://eccc.weizmann.ac.il/report/2003/038