All reports by Author Seffi Naor:

__
TR03-038
| 15th May 2003
__

Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor#### Asymmetric k-center is log^*n-hard to Approximate

Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor

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