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

| cite | improve this question | | | | |
$\endgroup$
  • 9
    $\begingroup$ $k^k$ is not a polynomial in $k$ $\endgroup$ – rici Mar 5 '13 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 Mar 5 '13 at 20:03
  • $\begingroup$ The million dollar hinges on whether $k$ is part of the input here. See also parametrised complexity. $\endgroup$ – Raphael♦ Mar 6 '13 at 7:01
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.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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