# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
: The bound on the working memory is an immediate consequence of Lemmas 1 and 2, and of the fact that \(|\Gamma|=O\Big{(}\log_{1+\beta}(d_{\max}/d_{\min})\Big{)}\). Procedure update is easily implemented through a constant number of linear scans of \(A_{\gamma}\), \(R_{\gamma}\), and \(O_{\gamma}\), for every \(\gamma\in\Gamma\), and a linear scan of, at most, one histogram. For what concerns Procedure extractCoreset, for each \(\gamma\in\Gamma\), the computation of \(C\) requires time quadratic in \(|A_{\gamma}|+|R_{\gamma}|+|O_{\gamma}|\), and the number of guesses \(\gamma\in\Gamma\) to be checked are at most \(|\Gamma|\) if a linear search is used, and \(O(\log(|\Gamma|))\) if binary search is used. In addition, time \(O(|T|)\) is needed to compute \(\hat{w}(r)\) for all \(r\in T\). Based on these considerations, the complexity bounds follow again from Lemmas 1 and 2 and the size of \(|\Gamma|\). ### Computation of the Solution from the Coreset

At any time \(t\), to compute a solution to the \(k\)-center problem with \(z\) outliers on the window \(W\), we first determine a weighted coreset \(T\), as explained in the previous subsection, and then, on \(T\), we run a sequential strategy for the weighted variant of the problem. To this purpose, we make use of the algorithm developed in [8; 9], which generalizes the sequential algorithm of [7] to the weighted case. Given as an input a weighted set \(T\), a value \(k\), a precision parameter \(\varepsilon\), and a radius \(\rho\), the algorithm computes a set \(X\) of \(k\) centers incrementally in, at most, \(k\) iterations. Initially, all points are considered _uncovered_. At each iteration, the next center is selected as the point that maximizes the aggregate weight of the yet uncovered points within distance \((1+2\varepsilon)\rho\), and such a center _covers_ all points in \(T\) within the larger distance \((3+4\varepsilon)\rho\). The algorithm terminates when either \(|X|=k\) or no uncovered points remain, returning \(X\) and the subset \(T^{\prime}\) of uncovered points. This algorithm is implemented by procedure outliersCluster\((T,k,\rho,\varepsilon)\). The next lemma states an important property related to the use of outliersCluster (Algorithm 5) in our context. ```
1\(T^{\prime}=T\)
2\(X=\emptyset\)while\(|X|<k\) and \(T^{\prime}\
eq\emptyset\)do
3 for\(r\in T\)do
4\(B_{r}=\{\varphi:\,v\in T^{\prime}\text{and dist}(v,r)\leq(1+2\varepsilon)\rho\}\)
5\(x=\operatorname*{argmax}_{\gamma\in T}\sum_{v\in B_{r}}\hat{w}(v)\)
6\(X=X\cup\{x\}\)
7\(E_{x}=\{v:\,v\in T^{\prime}\text{and dist}(v,x)\leq(3+4\varepsilon)\rho\}\)
8\(T^{\prime}=T^{\prime}\setminus E_{x}\) return\(X,T^{\prime}\)
```
**Algorithm 5**OutliersCluster\((T,k,\rho,\varepsilon)\)

**Lemma 3**. : _For any time \(t\), let \(T=R_{\hat{\gamma}}\cup O_{\hat{\gamma}}\) be the weighted coreset returned by extractCoreset\(()\). For any \(\rho\geq r_{k,z}^{*}(W)\), the invocation outliersCluster\((T,k,\rho,\varepsilon)\) with \(\varepsilon=4(1+\beta)\) returns a set of centers \(X\) and a set of uncovered points \(T^{\prime}\subseteq T\), such that_

* \(\operatorname*{dist}(r,X)\leq(3+4\varepsilon)\rho\quad\forall r\in T\setminus T ^{\prime}\)__
* \(\sum_{r\in T^{\prime}}\hat{w}(r)\leq z\)_._

Proof. : The proof can be obtained as a simple technical adaptation of the one of [9] [Lemma 5] to the case of approximate weights. For clarity, we detail the entire proof rather than highlighting the changes only. The bound on \(\operatorname*{dist}(r,X)\) for every \(r\in T\setminus T^{\prime}\) is directly enforced by the algorithm. We are left to show that \(\sum_{r\in T^{\prime}}\hat{w}(r)\leq z\). If \(|X|<k\), then \(T^{\prime}=\emptyset\) and the claim holds trivially. We now concentrate on the case \(|X|=k\). Consider the \(i\)-th iteration of the while loop of outliersCluster\((T,k,\rho,\varepsilon)\) and define \(x_{i}\) as the center of \(X\) selected in the iteration, and \(T_{i}^{\prime}\) as the set \(T^{\prime}\) of uncovered points at the beginning of the iteration.