# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
It has to be remarked that, although point \(p_{t-|W|}\) is not available at time \(t-1\), this is not a problem since the point immediately expires at time \(t\) and is removed from the data structures without even being used in the processing of \(p_{t}\). Hence, in this context, \(p_{t-|W|}\) acts as a mere placeholder. For what concerns the histogram \(L_{p_{t-1}}\) to associate with \(p_{t-1}\) (for every \(\gamma>\max\{\gamma^{\prime}\in\Gamma_{t-1}\}\)), its exact version represents the entire active window, and hence it would be the list \(\{(t-|W|,|W|),\ldots,(t-2,2),(t-1,1)\}\). In order to satisfy the properties of Lemma 2, \(L_{p_{t-1}}\) can be trimmed as follows. Let \(f(x)=\left\lceil\frac{x}{1+\lambda}\right\rceil\). Then, \(L_{p_{t-1}}\) contains the set of pairs \((t-c_{i},c_{i})\), with \(i\geq 0\), where the \(c_{i}\)s form a decreasing sequence of values \(\geq 1\) such that \(c_{0}=|W|\) and, for each \(i\leq 0\) with \(c_{i}>1\), \(c_{i+1}=\min\{c_{i}-1,f(c_{i})\}\). Lemma 4: _The list \(L_{p_{t-1}}\) defined above satisfies the properties stated in Lemma 2._

Proof: Property 1 clearly holds. As for Property 2, consider two consecutive pairs \((t-c_{i},c_{i})\) and \((t-c_{i+1},c_{i+1})\). If \(c_{i+1}=f(c_{i})\), then it is certain that \(c_{i}\leq(1+d)c_{i+1}\). Hence, when \(c_{i}>(1+\lambda)c_{i+1}\), we must have \(c_{i+1}=c_{i}-1\), and the property follows. Property 3 holds, since, for \(1\leq i\leq|L_{r}|-2\), \(c_{i+2}\leq c_{i+1}-1<(c_{Once the correct configurations of the data structures for all guesses \(\gamma\in\Gamma_{t}\) are obtained, Procedure \(\textsc{update}(p_{t},t)\) is invoked to complete step \(t\), thus enforcing the properties of Lemmas 1 and 2 for all of these data structures. ### Improved Approximation under Bounded Doubling Dimension

Consider a stream \(S\) of doubling dimension \(D\). We now outline an improved coreset construction that is able to provide a \(\delta\)-coreset \(T\) for the \(k\)-center problem with \(z\) outliers, for _any_ given \(\delta>0\), at the expense of a blow-up in the working memory size, which is analyzed as a function of \(D\) and is tolerable for small (e.g., constant) \(D\). This improved construction allows us to obtain a much tighter approximation for the \(k\)-center problem with \(z\) outliers in the sliding window setting. Fix any given \(\delta>0\). In [22], a refinement of the \(k\)-center strategy of [21] is presented that, for every guess \(\gamma\), maintains two families of attraction, representative, and orphan points. The first family, referred to as _validation points_, features three \(O(k)\)-sized sets of attraction, representative, and orphan points, equivalent to those described in Subection 3.1. Validation points are employed to identify a constant approximation \(\hat{\gamma}\) to the optimal radius \(r_{k}^{*}(W)\). The second family, referred to as _coreset points_, contains, for any guess \(\gamma\), three \"expanded\" sets of attraction, representative, and orphan points, which refine the coverage provided by the corresponding sets of validation points, in the sense that the coreset points relative to the guess \(\hat{\gamma}\) yield a coreset \(T\) such that \(\max_{p\in W}d(p,T)\leq\delta r_{k}^{*}(W)\). For each \(\gamma\), these larger sets contain \(O(k(c/\delta)^{D})\) points for a suitable constant \(c\). We can augment the algorithm of [22] in the same fashion as we augmented the algorithm of [21] by endowing the representative and orphan coreset points with the histograms described in Section 3.1. Then, by running the resulting algorithm for \(k+z\) (instead of \(k\)) centers, the result stated in the following lemma is immediately obtained, where parameter \(\lambda\) and functions \(w(\cdot)\) and \(\tilde{w}(\cdot)\) have the same meanings as before. Lemma 5: _Let \(\delta,\lambda>0\) be two design parameters.