6
$\begingroup$

I am currently confused by the following situation:

1) The metric $k$-center problem is inapproximable in polynomial time within $2-\epsilon$ unless $P=NP$.
2) The metric $k$-center problem can approximated within $1+\epsilon$ in time $O(k^{O(k/ \epsilon)})$

Did I just win a million dollars or why isn't this a contradiction? I guess my confusion comes from the unprecise statement "in polynomial time" in 1).

$\endgroup$
3
  • 9
    $\begingroup$ $k^k$ is not a polynomial in $k$ $\endgroup$
    – rici
    Commented Mar 5, 2013 at 19:32
  • 1
    $\begingroup$ but possibly constant in $n$. I guess that's where my problem lies, that to show hardness of approximation, $k$ will be a function of $n$ $\endgroup$
    – jack
    Commented Mar 5, 2013 at 20:03
  • $\begingroup$ The million dollar hinges on whether $k$ is part of the input here. See also parametrised complexity. $\endgroup$
    – Raphael
    Commented Mar 6, 2013 at 7:01

1 Answer 1

11
$\begingroup$

The first sentence says there is no approximation algorithm with $2-\epsilon$ for k-center, which means $k$ is part of an input, because there is no limitation on $k$, so $k$ can be arbitrary large (as $n$). This is common mistake in the context of approximation algorithms and parametrized complexity, this doesn't mean the algorithm runs in polynomial time, this says if you "fix" some parameters (e.g here k) you can have polynomial time algorithm, exactly like what you mentioned, mentioned algorithm is polynomial in $n$ but not in $k$, and when $k$ is not fix and is part of input, the algorithm is not polynomial. You can read more detail on fix parameter tractability in reference question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.