
\((1+\frac{2}{e}+\epsilon ) \approx (1.74+\epsilon )\) -approximation (resp. \(1+\frac{8}{e}+\epsilon )\) -approximation) for \(k\) -MedianOut (resp. \(k\) -MeansOut) in general metrics [1]}. These approximations are tight even for \(m = 0\) , under a reasonable complexity theoretic hypothesis, as shown in the same paper.

\((1+\epsilon )\) -approximation for \(k\) -MedianOut and \(k\) -MeansOut in (i) metric spaces of constant doubling dimensions, which includes Euclidean spaces of constant dimension, (ii) metrics induced by graphs of bounded treewidth, and (iii) metrics induced by graphs that exclude a fixed graph as a minor (such as planar graphs). [1]}.

\((2+\epsilon )\) -approximation for Matroid Median with Outliers in general metrics, where \(k\)  refers to the rank of the matroid. [3]}

\((1+\frac{2}{e}+\epsilon )\) -approximation for Colorful \(k\) -Median in general metrics, where \(m\)  denotes the total number of outliers across all color classes [3]}. The preceding two problems are orthogonal generalizations of \(k\) -MedianOut, and are formally defined in Section .

