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.
Asked
Active
Viewed 190 times
0
-
Your links were institution specific. I edited them. Just letting you know for the next time you post :-) – parsiad Feb 17 '19 at 00:17
1 Answers
0
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.
