# _k_-Center Clustering with Outliers in Sliding Windows
## 2 Preliminaries
### Definition of the Problems  
For any point \(p\in W\) and any subset \(C\subseteq W\), we use the notation \(\operatorname{dist}(p,C)=\min_{q\in C}\operatorname{dist}(p,q)\), and define the _radius of \(C\) with respect to \(W\)_ as  
\[r_{C}(W)=\max_{p\in W}\operatorname{dist}(p,C).\]  
For a positive integer \(k<|W|\), the \(k\)_-center problem_ requires finding a subset \(C\subseteq W\) of \(k\) centers that minimizes \(r_{C}(W)\). For a given \(W\) and \(k\), we denote the radius of the optimal solution of this problem by \(r_{k}^{*}(W)\). Given any radius value \(r\), a subset \(C\subseteq W\) with \(r_{C}(W)\leq 2r\) can be incrementally built using the _greedy strategy_ of [13]: starting from an arbitrary center, a new center selected among the points of \(W\) at a distance \(>2r\) from the current centers is iteratively added to \(C\) until all points of \(W\) are at a distance of at most \(2r\) from \(C\). An easy argument shows that, if \(r\geq r_{k}^{*}(W)\), the set \(C\) obtained in this fashion has a size of, at most, \(k\). By combining this strategy with a suitable guessing protocol, a 2-approximate solution to the \(k\)-center problem for \(W\) is obtained. Note that any subset \(C\subseteq W\) induces a partition of \(W\) into \(|C|\) clusters by assigning each point to its closest center (with ties broken arbitrarily). In this paper, we focus on the following important extension to the \(k\)-center problem. For positive \(k,z<|W|\), the \(k\)_-center problem with \(z\) outliers_ requires finding a subset \(C\subseteq W\) of size \(k\) minimizing \(r_{C}(W-Z_{C})\), where \(Z_{C}\) is the set of \(z\) points in \(W\) with the largest distances from \(C\), which are regarded as outliers to be discarded from the clustering. We denote the radius of the optimal solution of this problem by \(r_{k,z}^{*}(W)\). Observe that the \(k\)-center problem with \(z\) outliers reduces to the \(k\)-center problem for \(z=0\). In addition, it is straightforward to argue that the optimal solution of the \(k\)-center problem (without outliers) with \(k+z\) centers has a radius not larger than the optimal solution of the problem with \(k\) centers and \(z\) outliers, that is,  
\[r_{k+z}^{*}(W)\leq r_{k,z}^{*}(W). \tag{1}\]  
In a more general formulation of the \(k\)-center problem with \(z\) outliers, each point \(p\in W\) carries a positive integer weight \(w(p)\), and the desired set \(C\) of \(k\) centers must minimize \(r_{C}(W-Z_{C})\), where \(Z_{C}\) is the set of points with the largest distances from \(C\) of maximum cardinality and an aggregate weight of, at most, \(z\). We will refer to this weighted formulation as \(k\)_-center with \(z\) weighted outliers_. The algorithms presented in this paper for \(k\)-center with \(z\) outliers crucially rely on the extraction of a succinct _coreset_\(T\) from the (possibly large) input \(W\), so a solution to the problem can be efficiently computed by running a sequential algorithm on \(T\) rather than on \(W\). The quality of a coreset \(T\) is captured by the following definition. **Definition 1**. : _Given a pointset \(W\) and a value \(\varepsilon>0\), a subset \(T\subseteq W\) is an \(\varepsilon\)-coreset for \(W\) w.r.t. the \(k\)-center problem with \(z\) outliers if \(\max_{p\in W}\operatorname{dist}(p,T)\leq er^{*}_{k,z}(W)\)._  
An \(\varepsilon\)-coreset \(T\) of \(W\) ensures that each point in \(W\) is \"represented\" by a close enough point in \(T\), where closeness is defined w.r.t. \(\varepsilon\) and \(r^{*}_{k,z}(W)\). In fact, our algorithms will make use of _weighted coresets_, where, additionally, each coreset point \(p\in T\) features a weight that is (an approximation of) the number of points of \(W\) represented by \(p\). An important characteristic of a pointset \(W\) is its _diameter_, defined as \(\Delta_{W}=\max_{p,q\in W}\operatorname{dist}(p,q)\), which can be computed exactly in quadratic time.