This is similar to \(k\) -MedianOut, except that the cost function is the sum of squares of distances of all except \(m\)  outlier points to a set of \(k\)  facilities. This generalizes the well-known \(k\) -Means problem. Here, the main obstacle is that, the squares of distances do not satisfy triangle inequality, and thus it does not form a metric. However, they satisfy a relaxed version of triangle inequality (i.e., \(\mathsf {d}(p, q)^2 \le 2 (\mathsf {d}(p, r)^2 + \mathsf {d}(r, q)^2)\) ). This technicality makes the arguments tedious, nevertheless, we can follow the same approach as for \(k\) -MedianOut, to obtain optimal FPT approximation schemes. Our technique implies an optimal \((1+\frac{8}{e} + \epsilon )\) -approximation for \(k\) -MeansOut (using the result of [1]} as a black-box), improving upon polynomial-time \(53.002\) -approximation from [2]}, and \((9+\epsilon )\) -approximation from [3]} in time FPT in \(k, m\)  and \(\epsilon \) .
