The following table summarizes previous work along with our current results. By far, the most widely-studied problems in this class have been the \(k\) -median and \(k\) -means functions.
In general, the extension to arbitrary \(M\) -estimators is non-trivial; the first such result was [1]}. Our approach naturally lends itself to this extension. \(M\) -estimators are highly important for noisy data or data with outliers. As one example, Huber's estimator is widely used in the statistics community [2]}, [3]}. It was written that “this estimator is so satisfactory
that it has been recommended for almost all situations” [4]}. Our results work not only for Huber's estimator but for all \(M\) -estimators, such as the Cauchy and Tukey biweight functions which are also well-used functions.
