Bicriteria approximations relax the strict requirement of using at most \(k\)  centers, or dropping at most \(m\)  outliers, in order to give improved approximation ratios, or efficiency (or both). For \(k\) -MedianOut, Charikar et al. [1]} gave a \(4(1+1/\epsilon )\) -approximation, while dropping \(m(1+\epsilon )\)  outliers. Gupta et al. [2]} gave a constant approximation based on local search for \(k\) -MeansOut that drops \(O(km \log (n\Delta ))\)  outliers, where \(\Delta \)  is the diameter of the set of points. Friggstad et al. [3]} gave a \((25+\epsilon )\) -approximation that uses \(k(1+\epsilon )\)  centers but only drops \(m\)  outliers. In Euclidean spaces, they also give a \((1+\epsilon )\) -approximation that returns a solution with \(k(1+\epsilon )\)  centers.
