0
$\begingroup$

I am studying the Euclidean $k$-center problem. This paper proved that the problem is NP-hard for any arbitrary $k$. However, in this paper authors provided an algorithm for finding solutions for the $k$-center problem in $O(n^{O(\sqrt{k})})$ time. I am confused. If the problem is NP-hard, how we are getting that solution? I don't know whether I am missing something silly here.

$\endgroup$
  • $\begingroup$ Your links were institution specific. I edited them. Just letting you know for the next time you post :-) $\endgroup$ – parsiad Feb 17 at 0:17
0
$\begingroup$

If a problem is $NP$-hard, this means that it is (assuming $P$ is not equal to $NP$) impossible to compute the optimal solution in time polynomial in the inputsize.

because $k$ is part of the input the term $n^{O(\sqrt{k})}$ is not considered polynomial, because the exponent is not a constant but depends on the input.

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