1. An adaptive probabilistic algorithm for online k-center clustering
- Author
-
Ruiqi Yang, Yicheng Xu, Dachuan Xu, and Dongmei Zhang
- Subjects
0209 industrial biotechnology ,021103 operations research ,Control and Optimization ,Euclidean space ,Applied Mathematics ,Strategy and Management ,Competitive algorithm ,Minimum distance ,0211 other engineering and technologies ,Center (category theory) ,02 engineering and technology ,Atomic and Molecular Physics, and Optics ,Randomized algorithm ,Combinatorics ,020901 industrial engineering & automation ,ComputingMethodologies_DOCUMENTANDTEXTPROCESSING ,Partition (number theory) ,Business and International Management ,Electrical and Electronic Engineering ,Cluster analysis - Abstract
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.
- Published
- 2019