# Algorithm for Euclidean K-Center Problem

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.

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

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.