The first constant approximation for \(k\) -MedianOut was given by Chen [1]} for some large constant. More recently, [2]}, [3]} gave constant approximations based on iterative LP rounding technique, and the \(6.994\) -approximation by Gupta et al. [3]} is currently the best known approximation. These approximation algorithms run in polynomial time in \(n\) . Krishnaswamy et al. [2]} also give the best known polynomial approximations for related problems of \(k\) -MeansOut and Matroid Median.
