# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
To this purpose, we first observe that \(B_{\pi_{\hat{\gamma}}(o_{i})}\) contains \(\{\pi_{\hat{\gamma}}(u):u\in C_{o_{i}}\}\cap T^{\prime}_{i}\), since, for each \(u\in C_{o_{i}}\),

\[d(\pi_{\hat{\gamma}}(o_{i}),\pi_{\hat{\gamma}}(u)) \leq d(\pi_{\hat{\gamma}}(o_{i}),o_{i})+d(o_{i},u)+d(u,\pi_{\hat{ \gamma}}(u))\] \[O\left(\log_{1+\beta}(d_{\max}/d_{\min})\cdot\left((k+z)+\log_{1+\lambda}(|W|) \right)\right),\]0

Therefore, the aggregate approximate weight of \(B_{\pi_{\hat{\gamma}}(o_{i})}\) is at least \(\big{|}\big{\{}u\in C_{o_{i}}:\pi_{\hat{\gamma}}(u)\in T^{\prime}_{i}\big{\}} \big{|}\). Since Iteration \(i\) selects \(x_{i}\) as the center, such that \(B_{x_{i}}\) has maximum aggregate approximate weight, we have that

\[O\left(\log_{1+\beta}(d_{\max}/d_{\min})\cdot\left((k+z)+\log_{1+\lambda}(|W|) \right)\right),\]1

hence, the points \(u\in C_{o_{i}}\) with \(\pi_{\hat{\gamma}}(u)\in T^{\prime}_{i}\) can be charged to the points in \(B_{x_{i}}\), since \(B_{x_{i}}\) has enough aggregate approximate weight. Note that the points of \(B_{x_{i}}\) did not receive any charging by Rule 1 in previous iterations, since they are uncovered at the beginning of Iteration \(i\), and will not receive chargings by Rule 1 in subsequent iterations, since \(B_{x_{i}}\) does not intersect the set \(C_{o}\) of any optimal center \(o\) yet to be chosen. In addition, no further charging to the points of \(B_{x_{i}}\) by Rule 2 will happen in subsequent iterations, since Rule 2 will only target sets \(B_{x_{k}}\) with \(h>i\). These observations ensure that any point of \(T\) receives charges through either Rule 1 or Rule 2, but not both, and never in excess of its weight, and the proof follows. At any time \(t\), to obtain the desired solution, we invoke Procedure computeSolution, which works as follows (see Algorithm 6 for the pseudocode). The procedure first extracts the coreset \(T=R_{\hat{\gamma}}\cup O_{\hat{\gamma}}\) calling extractCoreset. Then, it sets \(\varepsilon=4(1+\beta)\) and runs \(\textsc{outliersCluster}(T,k,\rho,\epsilon)\) for a geometric sequence of values of \(\rho\) between \(d_{\min}\) and \(d_{\max}\), with step \(1+\beta\), stopping at the minimum value \(\rho_{min}\) for which the pair \((X,T^{\prime})\) returned by \(\textsc{outliersCluster}(T,k,\rho_{min},\varepsilon)\) is such that the aggregate approximate weight of set \(T^{\prime}\) is, at most, \(z\). (Note that the parameter \(\beta\) in the definitions of \(\varepsilon\) and of the step used in the geometric search for \(\rho_{min}\) is the same one that appears in the definition of \(\Gamma\); hence, \(\beta\in(0,1]\).) At this point, the set of centers \(X\) is returned as a solution to the \(k\)-center problem with \(z\) outliers on the current window \(W\). ```
1\(T\leftarrow\textsc{extractCoreset}()\)
2\(\rho\leftarrow d_{\min}\)
3\(\epsilon\leftarrow\)\(4(1+\beta)\)
4\((X,T^{\prime})\leftarrow\textsc{outliersCluster}(T,k,\rho,\epsilon)\)
5\(\bar{w}(T^{\prime})\leftarrow\sum_{r\in T}\bar{w}(r)\)
6 while\(\bar{w}(T^{\prime})>z\)do
7\(\rho\leftarrow\rho\cdot(1+\beta)\)
8\((X,T^{\prime})\leftarrow\textsc{outliersCluster}(T,k,\rho,\epsilon)\)
9\(\bar{w}(T^{\prime})\leftarrow\sum_{r\in T}\bar{w}(r)\) return\(X\)
```

**Algorithm 6**computeSolution()

The following theorem highlights the tradeoff between the accuracy (in terms of both the radius and excess number of outliers) and the performance exhibited by computeSolution. Theorem 3: _At any time \(t\), computeSolution returns a set \(X\subseteq W\) of, at most, \(k\) centers, such that at least \(|W|-(1+\lambda)z\) points of \(W\) are at a distance of, at most, \((23+55\beta)r_{k,z}^{*}(W)\) from \(X\).