AN ADAPTIVE PROBABILISTIC ALGORITHM FOR ONLINE k-CENTER CLUSTERING

The k-center clustering is one of the well-studied clustering problems in computer science. We are given a set of data points P subset of R-d, where R-d is d dimensional Euclidean space. We need to select k <= vertical bar P vertical bar points as centers and partition the set P into k clusters with each point connecting to its nearest center. The goal is to minimize the maximum radius. We consider the so-called online k-center clustering model where the data points in R-d arrive over time. We present the bi-criteria (n/k , (log U*/L* )(2))-competitive algorithm and (n/k,log gamma log n gamma/k)-competitive algorithm for semi-online and fully-online k-center clustering respectively, where U* is the maximum cluster radius of optimal solution, L* is the minimum distance of two distinct points of P, gamma is the ratio of the maximum distance of two distinct points and the minimum distance of two distinct points of P and n is the number of points that will arrive in total.