# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
Recall that \(x_{i}\) is the point of \(T\) that maximizes the cumulative approximate weight of the set \(B_{x_{i}}\) of uncovered points in \(T_{i}^{\prime}\) at a distance of, at most, \((1+2\varepsilon)\cdot\rho\) from \(x_{i}\), and that the set \(E_{x_{i}}\) of all uncovered points at a distance of, at most, \((3+4\varepsilon)\cdot\rho\) from \(x_{i}\) is removed from \(T_{i}^{\prime}\) at the end of the iteration. Let

\[\sigma_{T}=\sum_{r\in T}\widehat{w}(r).\]

We now show that

\[\sum_{i=1}^{k}\sum_{r\in E_{x_{i}}}\widehat{w}(r)\geq\sigma_{T}-z, \tag{2}\]

which will immediately imply that \(\sum_{r\in T}\widehat{w}(r)\leq z\). To this purpose, let \(O\) be an optimal set of \(k\) centers for the current window \(W\), and let \(Z\) be the set of, at most, \(z\) outliers at a distance greater than \(r_{k,z}^{*}(W)\) from \(O\). Let also \(\tilde{W}\) be a subset of the current window that, for every \(r\in T\), contains exactly \(\widehat{w}(r)\) points \(q\), including \(r\), for which \(r\) is a proxy, that is, points \(q\in W\) such that \(\pi_{\tilde{\gamma}}(q)=r\). Note that \(\tilde{W}\) is well defined since, by Theorem 1, \(\widehat{w}(r)\) is always less than or equal to the actual weight of \(r\). For each \(o\in O\), define \(C_{o}\subseteq\tilde{W}\setminus Z\) as the set of nonoutlier points in \(\tilde{W}\) that are closer to \(o\) than to any other center of \(O\), with ties broken arbitrarily. It is important to remark, that while there may be some optimal center \(o\in O\) that is not in \(\tilde{W}\), its proxy \(\pi_{\tilde{\gamma}}(o)\) is in \(T\); hence, it is guaranteed to be in \(\tilde{W}\). To prove Equation (2), it is sufficient to exhibit an ordering \(o_{1},o_{2},\ldots,o_{k}\) of the centers in \(O\) so that, for every \(1\leq i\leq k\), it holds

\[\sum_{j=1}^{i}\sum_{r\in E_{x_{j}}}\widehat{w}(r)\geq|C_{o_{1}}\cup\cdots\cup C _{o_{i}}|.\]

The proof uses an inductive charging argument to assign each point in \(\bigcup_{j=1}^{i}C_{o_{j}}\) to a point in \(\bigcup_{j=1}^{i}E_{x_{j}}\), where each \(r\) in the latter set will be in charge of, at most, \(\widehat{w}(r)\) points. We define two charging rules. A point can be either charged to its own proxy (_Rule 1_) or to another point of \(T\) (_Rule 2_). Fix some arbitrary \(i\), with \(1\leq i\leq k\), and assume, inductively, that the points in \(C_{o_{1}}\cup\cdots\cup C_{o_{i-1}}\) have been charged to points in \(\bigcup_{j=1}^{i-1}E_{j}\) for some choice of distinct optimal centers \(o_{1},o_{2},\ldots,o_{i-1}\). We have two cases. **Case 1. ** There exists an optimal center \(o\) still unchosen such that there is a point \(v\in C_{o}\) with \(\pi_{\tilde{\gamma}}(v)\in B_{x_{j}}\), for some \(1\leq j\leq i\). We choose \(o_{i}\) as one such center. Hence, \(d(x_{j},\pi_{\tilde{\gamma}}(v))\leq(1+2\varepsilon)\cdot\rho\). By repeatedly applying the triangle inequality, we have that, for each \(u\in C_{o_{i}}\),

\[d(x_{j},\pi_{\tilde{\gamma}}(u))\leq d(x_{j},\pi_{\tilde{\gamma}}(v))+d(\pi_{\tilde{\gamma}}(v),v)+d(v,o_{i})\] \[+d(o_{i},u)+d(u,\pi_{\tilde{\gamma}}(u))\leq(3+4\varepsilon)\cdot\rho\]

hence, \(\pi_{\tilde{\gamma}}(u)\in E_{x_{j}}\). Therefore we can charge each point \(u\in C_{o_{i}}\) to its proxy by Rule 1. **Case 2. ** For each unchosen optimal center \(o\) and each \(v\in C_{o}\), \(\pi_{\tilde{\gamma}}(v)\
ot\in\bigcup_{j=1}^{i}B_{x_{j}}\). We choose \(o_{i}\) to be the unchosen optimal center that maximizes the cardinality of \(\{\pi_{\tilde{\gamma}}(u):u\in C_{o_{i}}\}\cap T_{i}^{\prime}\). We distinguish between points \(u\in C_{o_{i}}\) with \(\pi_{\tilde{\gamma}}(u)\
otin T_{i}^{\prime}\); hence, \(\pi_{\tilde{\gamma}}(u)\in\bigcup_{j=1}^{i-1}E_{x_{j}}\), and those with \(\pi_{\tilde{\gamma}}(u)\in T_{i}^{\prime}\). We charge each \(u\in C_{o_{i}}\) with \(\pi_{\tilde{\gamma}}(u)\
otin T_{i}^{\prime}\) to its own proxy by Rule 1. As for the other points, we now show that we can charge them to the points of \(B_{x_{i}}\).