A result that initiated this study is an exact algorithm for \(k\) -center We note that the result of [1]} holds for a slightly different variant, where the centers can be placed anywhere in \(\mathbb {R}^d\) . This formulation is more natural and standard in euclidean spaces. by Agarwal and Procopiuc [1]}, who give an \(n^{\mathcal {O}(k^{1-\frac{1}{d}})}\)  time algorithm in \(\mathbb {R}^d\) . In particular, in two dimensional space, their algorithm runs in \(2^{\mathcal {O}(\sqrt{n} \log n)}\)  time for any value of \(k\) , i.e., in sub-exponential time. This led us towards a natural question, namely, studying the complexity of \(k\) -median, \(k\) -means, \(k\) -center in general metrics.
