# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
The procedure requires a working memory of size \(O\Big{(}(k+z)\log_{1+\beta}(d_{\max}/d_{\min})\log_{1+\lambda}(|W|)\Big{)}\) and runs in time_

\[O\left(\log_{1+\beta}(d_{\max}/d_{\min})\cdot\left((k+z)+\log_{1+\lambda}(|W|) \right)\right),\]2_If the while loop is substituted by a binary search for \(\rho_{min}\), the running time decreases to_

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

Proof. : Let \(\rho_{min}\) be such that \(\textsc{outliersCluster}(T,k,\rho_{min},\varepsilon)\) yields \((X,T^{\prime})\), where \(X\) is the returned solution, and let \(W^{\prime}\) be the set of points of \(W\) whose proxies are in \(T^{\prime}\). By Lemma 3 and the choice of the step of the geometric search for \(\rho_{min}\), we have that \(\rho_{min}\leq(1+\beta)r_{k,z}^{*}(W)\); hence, for each \(p\in W-W^{\prime}\), \(\mathrm{dist}(\pi_{\hat{\gamma}}(p),X)\leq(3+4\varepsilon)\rho_{min}\leq(3+4 \varepsilon)(1+\beta)r_{k,z}^{*}(W)\). Since \(T\) is an \(\varepsilon\)-coreset (Theorem 1) and \(\beta\in(0,1]\), we conclude that, for every \(p\in W-W^{\prime}\),

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

Moreover, by Theorem 1, we also have that \(|W^{\prime}|\leq(1+\lambda)\sum_{r\in T^{\prime}}\tilde{w}(r)\leq(1+\lambda)z\). The working memory bound is an immediate consequence of Theorem 2, since the working memory is dominated by the data structures from which the coreset is extracted. For what concerns the running time, observe that \(\textsc{outliersCluster}\) can be easily implemented to run in time \(O\big{(}k\cdot|T|^{2}\big{)}\), which is \(O\big{(}k\cdot(k+z)^{2}\big{)}\), since \(|T|=O(k+z)\) by Theorem 1. Therefore, the bound on the running time follows, since \(\textsc{extractCoreset}\) requires time \(O\Big{(}\log(\log_{1+\beta}(d_{\max}/d_{\min}))\cdot(k+z)^{2}\Big{)}\) (by Theorem 2), and the while loop performs, at most, \(O\Big{(}\log_{1+\beta}(d_{\max}/d_{\min})\Big{)}\) executions of \(\textsc{outliersCluster}\), which can be lowered to \(O\Big{(}\log\log_{1+\beta}(d_{\max}/d_{\min})\Big{)}\) using binary search. The above result shows that allowing for a slight excess in the number of outliers governed by parameter \(\lambda\) results in improved space and time complexities. Note that if the upper bound \(z\) on the number of outliers must be rigidly enforced, it is sufficient to set \(\lambda=1/(2z)\). In this case, \((1+\lambda)z=z+1/2\), and since the number of outliers must be an integer, it cannot be larger than \(z\). The following corollary is an immediate consequence of Theorem 3, of this observation, and of the fact that \(\log_{1+\lambda}x=\Theta((1/\lambda)\log x)\) for \(\lambda\in(0,1)\). **Corollary 1**. : _Let \(\lambda=1/(2z)\). At any time \(t\), computeSolution returns a set \(X\subseteq W\) of, at most, \(k\) centers, such that at least \(|W|-z\) points of \(W\) are at a distance of, at most, \((23+55\beta)r_{k,z}^{*}(W)\) from \(X\). The procedure requires a working memory of size \(O\Big{(}z(k+z)\log_{1+\beta}(d_{\max}/d_{\min})\log(|W|)\Big{)}\) and runs in time_

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

_If the while loop is substituted by a binary search for \(\rho_{min}\), the running time decreases to_

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

### Obliviousness to \(d_{\min}\) and \(d_{\max}\)

The algorithm described in Sections 3.1 and 3.2 requires the knowledge of the values \(d_{\min}\) and \(d_{\max}\). In this subsection, we show how to remove this requirement by employing the techniques developed in [22], suitably extended to cope with histograms, which were not used in that work.