## 5 \(k\)-Means with \(m\) Outliers
Applying this solution on our suggested coreset as explained in Corollary 3 might reduce this dependency on \(n\) from cubic to linear, due to the fact that its construction time which is linear in \(n\) and also polynomial in \(k+m\). In order to obtain a more general result for any \(\rho\)-distance, as in the previous section, we use a simple exhaustive search that takes time exponential in \(k+m\) but still \(O(n)\) for every constant \(k,m\) and \(\rho\). Our solution also implies streaming, parallel algorithm for \(k\)-median with \(m\) outliers on distributed data. This is simply because many \(k\)-median algorithms exist for these computation models, and they can be used to construct the \"coreset\" in Theorem 4.2 after replacing \(k\) with \(k+m\). An existing offline nonparallel solution for the \(k\)-median with \(m\) outliers, e.g., from the previous paragraph, may then be applied on the resulting coreset to extract the final approximation as explained in Corollary 4. For every point \(p\in P\), let \(\operatorname{proj}(p,Y)\in Y\) denote its closest point in \(Y\). For a subset \(Q\) of \(P\), define \(\operatorname{proj}(Q,Y)=\{\operatorname{proj}(p,Y)\mid p\in Q\}\) to be the union (multiset) of its \(|Q|\) projection on \(Y\). Ties are broken arbitrarily. Recall the definition of \(P_{X},C_{X}\) and \(\alpha\)-approximation from Definition 4. We now ready to prove the main technical result for the \(k\)-median with \(m\) outliers. **Theorem 4.2** (coreset for \(k\)-median with \(m\) outliers). : _Let \((P,f)\) be a \((\rho,\phi,\varepsilon)\) metric space, and let \(n=|P|\). Let \(k,m\in[n]\) such that \(k+m<n\), and let \(Y\) be an \(\alpha\)-approximation for the \((k+m)\)-median of \(P\) (without outliers). Let \(C:=\operatorname{proj}(P,Y)\). Then for every set \(X\subseteq P\) of \(|X|=k\) centers, we have_  
\[|f(P_{X},X)-f(C_{X},X)|\leq\left((\phi+\varepsilon\rho)\alpha+\varepsilon\rho \right)f(P_{X},X), \tag{44}\]  
_and_  
\[f(P_{X},X)\leq(1+\varepsilon\rho)f(C_{X},X)+(\phi+\varepsilon\rho)\alpha f^{ *}(P,k+m). \tag{45}\]  
Proof. : Let \(X\subseteq P\) be a set of \(|X|=k\) centers. The multiset \(\operatorname{proj}(P_{X},Y)\) contains \(n-m\) points that are contained in the \(k\) centers of \(Y\). However, we do not know how to approximate the number of copies of each center in \(\operatorname{proj}(P_{X},Y)\) without using \(P_{X}\). One option is to guess \((1+\varepsilon)\) approximation to the weight of each of these \(k+m\) points, by observing that it is \((1+\varepsilon)^{i}\) for some \(i\in O(\log(n)/\varepsilon)\), and then using exhaustive search. However, the running time would be exponential in \(k+m\) and the weights depend on the query \(X\). Instead, we observe that while we cannot compute \(\text{proj}(P_{X},Y)\) via \(\mathcal{C}\), we have the upper bound \(f(C_{X},X)\leq f(\text{proj}(P_{X},Y),X)\). It follows from the fact that  
\[\text{proj}(P_{X},Y)\subseteq\text{proj}(P,Y)=\mathcal{C},\]  
and \(|\text{proj}(P_{X},Y)|=n-m\), so  
\[f(C_{X},X)=\min_{Q\subseteq C,|Q|=n-m}f(Q,X)\leq f(\text{proj}(P_{X},Y),X). \tag{46}\]  
We now bound the rightmost term. For a single point \(p\in P\) we have  
\[|f(p,X)-f(\text{proj}(p,Y),X)| \leq(\phi+\varepsilon\rho)f(p,\text{proj}(p,Y))+\varepsilon\rho \min\left\{f(p,X),f(\text{proj}(p,Y),X)\right\} \tag{47}\] \[=(\phi+\varepsilon\rho)f(p,Y)+\varepsilon\rho\min\left\{f(p,X),f (\text{proj}(p,Y),X)\right\}, \tag{48}\]  
where (47) holds by substituting \(x=f(p,X)\) and \(y=f(\text{proj}(p,Y),X)\) (or vice vera) and \(Z=X\) in Lemma 2, and (48) holds by the definition of \(f(p,Y)\).