On the lower bound side, Guha and Khuller [1]} showed it is NP-hard to approximate \(k\) -Median (and thus \(k\) -MedianOut) within a factor \(1+\frac{2}{e}-\epsilon \)  for any \(\epsilon > 0\) . Recently, Cohen-Addad et al. [2]} strengthened this result assuming Gap-ETH, and showed that an \((1+\frac{2}{e}-\epsilon )\) -approximation algorithm must take at least \(n^{k^{g(\epsilon )}}\)  time for some function \(g()\) .
