An adaptive probabilistic algorithm for online k-center clustering
Ruiqi Yang, Dachuan Xu, Yicheng Xu, Dongmei Zhang · Journal of Industrial and Management Optimization · 2018
The \begin{document}$k$\end{document} -center clustering is one of the well-studied clustering problems in computer science. We are given a set of data points \begin{document}$P\subseteq R^d$\end{document} , where \begin{document}$R^d$\end{document} is \begin{document}$d$\end{document} dimensional Euclidean space. We need to select \begin{document}$k≤ |P|$\end{document} points as centers and partition the set \begin{document}$P$\end{document} into \begin{document}$k$\end{document} clusters with each point connecting to its nearest center. The goal is to minimize the maximum radius. We consider the so-called online \begin{document}$k$\end{document} -center clustering model where the data points in \begin{document}$R^d$\end{document} arrive over time. We present the bi-criteria \begin{document}$(\frac{n}{k}, (\log\frac{U^*}{L^*})^2)$\end{document} -competitive algorithm and \begin{document}$(\frac{n}{k}, \logγ\log\frac{nγ}{k})$\end{document} -competitive algorithm for semi-online and fully-online \begin{document}$k$\end{document} -center clustering respectively, where \begin{document}$U^*$\end{document} is the maximum cluster radius of optimal solution, \begin{document}$L^*$\end{document} is the minimum distance of two distinct points of \begin{document}$P$\end{document} , \begin{document}$γ$\end{document} is the ratio of the maximum distance of two distinct points and the minimum distance of two distinct points of \begin{document}$P$\end{document} and \begin{document}$n$\end{document} is the number of points that will arrive in total.