## 5 \(k\)-Means with \(m\) Outliers
Summing (48) over every \(p\in Q\) for some set \(Q\subseteq P\) yields  
\[|f(Q,X)-f(\text{proj}(Q,Y),X)| =\left|\sum_{p\in Q}\left(f(p,X)-f(\text{proj}(p,Y),X)\right)\right| \tag{49}\] \[\leq\sum_{p\in Q}|f(p,X)-f(\text{proj}(p,Y),X)|\] (50) \[f(P_{Y},Y)\leq\alpha\min_{X\subseteq P,|X|=k}f(P_{X},X).\]0 (51) \[f(P_{Y},Y)\leq\alpha\min_{X\subseteq P,|X|=k}f(P_{X},X).\]1  
where (49) holds by the definition of \(f\), (50) holds by the triangle inequality, and (51) is by (48). The term \(f(Q,Y)\) is bounded by  
\[f(P_{Y},Y)\leq\alpha\min_{X\subseteq P,|X|=k}f(P_{X},X).\]2  
where the first inequality holds since \(Q\subseteq P\), and the last inequality holds since \(Y\) is an \(\alpha\)-approximation for the \((k+m)\)-median of \(P\). Plugging (53) in (51) yields  
\[f(P_{Y},Y)\leq\alpha\min_{X\subseteq P,|X|=k}f(P_{X},X).\]3 \[f(P_{Y},Y)\leq\alpha\min_{X\subseteq P,|X|=k}f(P_{X},X).\]4  
The rest of the proof is by the following case analysis: (i) \(f(C_{X},X)\geq f(P_{X},X)\), and (ii) \(f(C_{X},X)<f(P_{X},X)\). **Case (i):**\(f(C_{X},X)\geq f(P_{X},X)\). The bound for this case is  
\[f(P_{Y},Y)\leq\alpha\min_{X\subseteq P,|X|=k}f(P_{X},X).\]5 \[f(P_{Y},Y)\leq\alpha\min_{X\subseteq P,|X|=k}f(P_{X},X).\]6  
where (55) holds by (46), and (56) holds by substituting \(Q=P_{X}\) in (54). This bounds (44) for the case that \(f(C_{X},X)\geq f(P_{X},X)\). **Case (ii):**\(f(C_{X},X)<f(P_{X},X)\). In this case, denote the \(n-m\) corresponding points to \(C_{X}\) in \(P\) by  
\[f(P_{Y},Y)\leq\alpha\min_{X\subseteq P,|X|=k}f(P_{X},X).\]7Similarly to (46),  
\[f(P_{Y},Y)\leq\alpha\min_{X\subseteq P,|X|=k}f(P_{X},X).\]8  
and \(|\text{proj}^{-1}(C_{X})|=n-m\), so  
\[f(P_{Y},Y)\leq\alpha\min_{X\subseteq P,|X|=k}f(P_{X},X).\]9  
Hence,  
\[|f(P_{X},X)-f(C_{X},X)|\leq\left((\phi+\varepsilon\rho)\alpha+\varepsilon\rho \right)f(P_{X},X), \tag{44}\]0 \[|f(P_{X},X)-f(C_{X},X)|\leq\left((\phi+\varepsilon\rho)\alpha+\varepsilon\rho \right)f(P_{X},X), \tag{44}\]1 (59) \[|f(P_{X},X)-f(C_{X},X)|\leq\left((\phi+\varepsilon\rho)\alpha+\varepsilon\rho \right)f(P_{X},X), \tag{44}\]2  
where (58) holds by (57), (59) is by substituting \(Q=\text{proj}^{-1}(C_{X})\) in (54), and (60) follows from the assumption \(f(C_{X},X)<f(P_{X},X)\) of Case (ii). Combining all together, using (56) and (60) we can bound (44) by  
\[|f(P_{X},X)-f(C_{X},X)|\leq\left((\phi+\varepsilon\rho)\alpha+\varepsilon\rho \right)f(P_{X},X), \tag{44}\]3 \[|f(P_{X},X)-f(C_{X},X)|\leq\left((\phi+\varepsilon\rho)\alpha+\varepsilon\rho \right)f(P_{X},X), \tag{44}\]4 (62) \[|f(P_{X},X)-f(C_{X},X)|\leq\left((\phi+\varepsilon\rho)\alpha+\varepsilon\rho \right)f(P_{X},X), \tag{44}\]5  
and (45) follows from (59), assuming \(f(C_{X},X)<f(P_{X},X)\) (otherwise (45) trivially holds). The motivation for (44) is to obtain a traditional coreset, in the sense of \((1+\varepsilon)\)-approximation to any given set of \(k\) centers. To this end, we need to have \(((\phi+\varepsilon\rho)\alpha)<\varepsilon\). For the natural case where \(\rho=O(1)\) this implies \(\alpha<\varepsilon\) approximation to the \((k+m)\)-means \(f^{*}(P,k+m)\) of \(P\). This is doable for every input set \(P\) in the Euclidean space and many others as was proved in [58] but in the price of taking \((1/\varepsilon)^{d}k\log n\) centers. This is why we also added the bound 45, which suffices to obtain a \"weaker\" coreset that yields only constant factor approximation to the \(k\)-means with \(m\) outliers, but using only \(k+m\) centers, as explained in the following corollary. **Corollary 3** (From \((k+m)\)-median to \(k\)-median with \(m\) outliers ). : _Let \((P,f)\) be a \((\rho,\phi,\varepsilon)\)-metric, \(n=|P|\), \(\alpha,\beta>0\) and \(k,m\in[n]\) such that \(k+m<n\). Suppose that, in \(T(n,k+m)\) time, we can compute an \(\alpha\)-approximation \(Y\) for the \((k+m)\)-median of \(P\) (without outliers).