# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
The authors wish to thank the anonymous referees for their constructive criticism that helped to improve the quality of the paper. The authors declare no conflict of interest. ## References

* (1) [PERSON]; [PERSON]; [PERSON] Computing on Data Streams. In Proceedings of the DIMACS Workshop on External Memory Algorithms, New Brunswick, NJ, USA, 20-22 May 1998; pp. 107-118. Cited by: SS1. * (2) [PERSON]; [PERSON] The Sliding-Window Computation Model and Results. In Data Stream Management, [PERSON], [PERSON], Springer: Berlin/Heidelberg, Germany, pp. 149-165. Cited by: SS1. * (3) [PERSON] Sliding Window Algorithms. In Encyclopedia of Algorithms, [PERSON], [PERSON], and [PERSON]; Springer: Berlin/Heidelberg, Germany, pp. 2006-2011. Cited by: SS1. * (4) [PERSON] Introduction to facility location. In Wiley Enciclopedia of Operations Research and Management Science, Wiley: Hoboken, NJ, USA, pp. 11. Cited by: SS1. * (5) [PERSON]; [PERSON]; [PERSON]; [PERSON] _Handbook of Cluster Analysis_; CRC Press: Boca Raton, FL, USA, 2015. Cited by: SS1. * (6) [PERSON]; [PERSON]; [PERSON]; [PERSON] Extreme k-Center Clustering. In Proceedings of the 35 th AAAI Conference on Artificial Intelligence (AAAI), Vancouver, BC, Canada, 2-9 February 2021; pp. 3941-3949. Cited by: SS1. * (7) [PERSON]; [PERSON]; [PERSON], [PERSON] Algorithms for Facility Location Problems with Outliers. In Proceedings of the 12 th ACM-SIAM Symposium on Discrete Algorithms (SODA), Washington, DC, USA, 7-9 January 2001; pp. 642-651. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Dataset** & **Eff. Diameter** & **Memory (\(\times 10^{6}\) floats)** & **Update Time (ms)** & **Query Time (s)** \\ \hline \(R=10\) & \(1.175\pm 0\) & \(0.22\pm 0.05\) & \(0.91\pm 0.31\) & \(1.69\pm 0.5\) \\ \(R=100\) & \(1.175\pm 0.006\) & \(0.24\pm 0.11\) & \(1.79\pm 1.01\) & \(0.84\pm 0.25\) \\ \(R=1000\) & \(1.178\pm 0.006\) & \(0.35\pm 0.14\) & \(1.9\pm 1.39\) & \(4.2\pm 1.34\) \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Effective diameter: sensitivity to \(\eta\). * _[PERSON] et al. (2015)_ [PERSON]; [PERSON] [PERSON]; [PERSON]; [PERSON] [PERSON]; [PERSON] Fast Distributed k-Center Clustering with Outliers on Massive Data. In Proceedings of the 28 th Conference on Neural Information Processing Systems (NIPS), Montreal, QC, Canada, 7-12 December 2015; pp. 1063-1071. * [PERSON] et al. (2018) [PERSON]; [PERSON] [PERSON]; [PERSON] [PERSON] Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially. _arXiv_**2018**, arXiv:1802.09205. * [PERSON] (1987) [PERSON]. Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis. _Comput. Appl. Math._**1987**, _20_, 53-65. [CrossRef]
* [PERSON] et al. (2021) [PERSON]; [PERSON]; [PERSON] [PERSON]; [PERSON] Scalable Distributed Approximation of Internal Measures for Clustering Evaluation. In Proceedings of the SIAM International Conference on Data Mining (SDM), Online, 29 April-1 May 2021; pp. 648-656. * [PERSON] (1985) [PERSON] Clustering to minimize the maximum intercluster distance. _Theor. Comput. Sci._**1985**, _38_, 293-306. [CrossRef]
* [PERSON] and [PERSON] (1985) [PERSON]; [PERSON] A Best Possible Heuristic for the \(k\)-Center Problem. _Math. Oper. Res._**1985**, _10_, 180-184. [CrossRef]
* [PERSON] et al. (2018) [PERSON]; [PERSON]; [PERSON] Fully Dynamic k-Center Clustering. In Proceedings of the World Wide Web Conference, Lyon, France, 23-27 April 2018; Volume 2018, pp. 579-587. * [PERSON] et al. (2019) [PERSON]; [PERSON]; [PERSON]; [PERSON] A Lottery Model for Center-Type Problems With Outliers. _ACM Trans. Algorithms_**2019**, _15_, 36. [CrossRef]
* [PERSON] et al. (2020) [PERSON]; [PERSON]; [PERSON] The Non-Uniform \(k\)-Center Problem. _ACM Trans. Algorithms_**2020**, _16_, 46. [CrossRef]
* [PERSON] et al. (2019) [PERSON]; [PERSON]; [PERSON] Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction.