# _k_-Center Clustering with Outliers in Sliding Windows
### Related Work  
In the sequential setting, the \(k\)-center problem (without outliers) admits simple \(2\)-approximation algorithms [12; 13]. Recently, a sequential, randomized, fully dynamic (i.e., admitting arbitrary insertions and deletions of points) \((2+\varepsilon)\)-approximation algorithm for the problem was presented in [14]. This algorithm features update times linear in \(k\) and \(1/\varepsilon\), and polylogarithmic in the _aspect ratio_\(\Delta=d_{\max}/d_{\min}\) of the pointset, that is, the ratio between the maximum distance \(d_{\max}\) and minimum distance \(d_{\min}\) of any two points in the set. For the \(k\)-center problem with \(z\) outliers, a simple, fully combinatorial \(3\)-approximation algorithm running in \(O(k|W|^{2}\log(|W|))\) time was devised in [7]. In [8; 9], an adaptation of this latter algorithm was proposed for weighted pointsets (where \(z\) represents the aggregate weight of the outliers). Recently, sequential \(2\)-approximation algorithms were developed in [15; 16] that, however, are based on a more complex LP-based approach that is less amenable to practical implementation. A bi-criteria randomized algorithm, which is only suitable for (small) constant \(k\), that returns a \(2\)-approximation as long as a slightly larger number of outliers is excluded from the objective function, was presented in [17]. For the classical streaming setting, which seeks, at any step, a solution for the _full_ stream seen so far, a \((4+\varepsilon)\)-approximation algorithm for the \(k\)-center problem with \(z\) outliers was given in [18]. The approximation was later improved to \(3+\varepsilon\) in [9]. Whereas the former algorithm requires \(O(\mathrm{k}z/\varepsilon)\) working memory space, the latter requires space \(O((k+z)(c/\varepsilon)^{D})\), where \(c\) is a constant and \(D\) is the _doubling dimension_ of the input stream, which is a widely used generalization of the notion of Euclidean dimension to arbitrary metrics [19; 20], and is formally defined in Section 2.2. For the stricter sliding window setting, in [21], the authors devised an algorithm able to compute a \((6+\varepsilon)\)-approximation to the \(k\)-center problem for the current window, while keeping \(O(k\log(\Delta)/\varepsilon)\) points stored in the working memory. Based on the same techniques, the authors also developed a \((3+\varepsilon)\)-approximation algorithm for the diameter of the current window. In [22], we presented a \((2+\varepsilon)\)-approximation algorithm for the \(k\)-center problem in the sliding window setting, where the improved approximation is obtained at the expense of a blow-up of a factor \(O((c/\varepsilon)^{D})\) in the working memory, with \(c\) constant. Concerning the \(k\)-center problem with \(z\) outliers in the sliding window setting, the only known algorithm was devised very recently in [23]. At every time step, the algorithm maintains an \(\varepsilon\)-coreset for the problem on the current window, namely, a subset of the window points, such that, if used as an input of any \(c\)-approximation sequential algorithm for \(k\)-center with \(z\) outliers, yields a \((c+\varepsilon)\)-approximate solution to the problem on the entire window. The algorithm requires the knowledge of the aspect ratio of the stream, and uses \(O\big{(}\log(\Delta)kz(1/\varepsilon)^{D}\big{)}\) working memory. Moreover, since it relies on the execution of a sequential algorithm for \(k\)-center with \(z\) outliers on the coreset every time a new point is added, it has an \(O\big{(}\log(\Delta)\big{(}kz(1/\varepsilon)^{D}\big{)}^{3}\big{)}\) update time per point, which makes it very impractical for streams with high arrival rates, and when values of \(k\) and \(z\) are not too small. In [23], the authors also prove that any sliding-window algorithm for \(k\)-center with \(z\) outliers, which features a \((1+\varepsilon)\) approximation ratio, must use \(\Omega(\log(\Delta)kz/\varepsilon)\) working memory.