## 5 \(k\)-Means with \(m\) Outliers  
In this section we consider the problem of \(k\)-means with \(m\) outliers of a given set \(P\), i.e., where the cost function for a given set \(X\) of \(k\) centers is \(f(P_{X},X)\) instead of \(f(P,X)\), and \(P_{X}\) is the subset of the closest \(n-m\) points to the centers. Ties are broken arbitrarily. That is, \(P\setminus P_{X}\) can be considered as the set of \(m\) outliers that are ignored in the summation of errors. **Definition 4** (\(k\)-median with \(m\) outliers). : _Let \((P,f)\) be a \(\rho\)-metric, \(n=|P|\), and \(k,m\in[n]\) be a pair of integers. For every subset \(Q\subseteq P\) of points in \(P\) and a set \(X\subseteq P\) of centers, denote by \(Q_{X}\) the closest \(n-m\) points to \(P\). A set \(X^{*}\) of \(k\) centers (points in \(P\)) is a \(k\)-median with \(m\) outliers of \(P\) if_  
\[f(P_{X^{*}},X^{*})\leq\min_{X\subseteq P_{i}|X|=k}f(P_{X},X).\]  
_For \(\alpha\geq 0\), a set \(Y\) is an \(\alpha\)-approximation to the \(k\)-median of \(P\) with \(m\) outliers if_  
\[f(P_{Y},Y)\leq\alpha\min_{X\subseteq P,|X|=k}f(P_{X},X).\]  
_Note that we allow \(Y\) to have \(|Y|>k\) centers._  
This is a harder and more general problem, since for \(m=0\) we get the \(k\)-median problem from the previous sections. We prove in this section that our generalized \(k\)-means++ can be served as a \"weaker\" type of coreset which admits an additive error that yields a constant factor approximation for the \(k\)-means with \(m\) outliers if \(\rho\) is constant. In fact, we prove that any approximated solution to the \((k+m)\)-median of \(P\) implies such a coreset, but Algorithm 1 is both simple and general for any \(\rho\)-distance. Moreover, by taking more than \(k+m\) centers, e.g., running Algorithm 1 additional iterations, we may reduce the approximation error \(\alpha\) of the coreset to obtain \"strong\" regular coreset, i.e., that introduces a \((1+\varepsilon)\)-approximation for any given query set \(X\) of \(k\) centers. This is by having an \(\alpha<\varepsilon\) approximation for the \((k+m)\) median; see Theorem 4. Upper and lower bounds for the number \(|X|\) of centers to obtain such \(\alpha<\varepsilon\) is the subject of [58]. The authors prove that a constant approximation to the \(|X|=O((1/\varepsilon)^{d}k\log n)\)-median of \(P\) yields such \(\alpha=O(\varepsilon)\)-approximation to the \(k\)-median. This implies that running Algorithm 1\(O((1/\varepsilon)^{d}(k+m)\log n)\) iterations would yield a coreset that admits \((1+\varepsilon)\)-approximation error for any given set of \(k\)-centers with their farthest \(m\) outliers, as traditional coresets. Unfortunately, the lower bounds of [58] show that the exponential dependency in \(d\) is unavoidable. However, the counter example is extremely artificial. In real world data, we may simply run Algorithm 1 until the approximation error \(f(P,|X|)\) is sufficiently small and hope this will happen after few \(|X|\) iterations due to the structure of the data. We state our result for the metric case and unweighted input. However, the proof essentially uses only the triangle inequality and its variants of Section 3. For simplicity of notation, we use the term multiset \(C\) instead of a weighted set \((C,w)\), where \(C\subseteq P\), and \(w:P\to[0,\infty)\) denote the number of copies of each item in \(C\). The size \(|C|\) of a multiset denotes its number of points (including duplicated points), unless stated otherwise. Unlike the case of \(k\)-means/median, there are few solutions to \(k\) means with \(m\) outliers. [PERSON] [50] provided a (multiplicative) constant factor approximation for the \(k\)-median with \(m\) outliers on any metric space (that satisfies the triangle inequality, i.e., with \(\rho=1\)) that runs in time \(O(n^{3}\log(n)dk^{2}(k+m)^{2})\), i.e., polynomial in both \(k\) and \(m\).