An adaptive probabilistic algorithm for online k-center clustering

Ruiqi Yang; Dachuan Xu; Yicheng Xu; Dongmei Zhang

doi:10.3934/jimo.2018057

Article Contents

2019, Volume 15, Issue 2: 565-576. Doi: 10.3934/jimo.2018057

This issue Previous Article RETRACTION: Peng Zhang, Chance-constrained multiperiod mean absolute deviation uncertain portfolio selection Next Article An uncertain programming model for single machine scheduling problem with batch delivery

An adaptive probabilistic algorithm for online k-center clustering

1.
Department of Information and Operations Research, College of Applied Sciences, Beijing University of Technology, Beijing 100124, China
2.
School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, China

* Corresponding author: Dongmei Zhang
* Corresponding author: Dongmei Zhang

Received: August 2017

Revised: December 2017

Early access: April 21, 2018

Published online: April 21, 2018

Abstract / Introduction Full Text(HTML) Figure(2) Related Papers Cited by

Abstract

The $k$-center clustering is one of the well-studied clustering problems in computer science. We are given a set of data points $P\subseteq R^d$, where $R^d$ is $d$ dimensional Euclidean space. We need to select $k≤ |P|$ 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 $(\frac{n}{k}, (\log\frac{U^*}{L^*})^2)$-competitive algorithm and $(\frac{n}{k}, \logγ\log\frac{nγ}{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$, $γ$ 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.

Keywords:

Mathematics Subject Classification: Primary: 90C27; Secondary: 68W27.

Citation:

Full Text(HTML)

Figure 1. An example of a sequence of points $1, x^2, ..., x^{2t}$ coming over time. The circles with dotted lines are the clusters produced by an online algorithm. Solid ones are those produced by the optimal off-line algorithm.

Download: Full-size image PowerPoint slide

Figure 2. An illustration of partition of $S^*_i$ for any given $i\in[k]$.

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	D. Achlioptas, M. Chrobak and J. Noga, Competitive analysis of randomized paging algorithms, Theoretical Computer Science, 234 (2000), 203-218. doi: 10.1016/S0304-3975(98)00116-9.
[2]	J. Bar-Ilan, G. Kortsarz and D. Peleg, How to allocate network centers, Journal of Algorithms, 15 (1993), 385-415. doi: 10.1006/jagm.1993.1047.
[3]	M. Charikar, C. Chekuri, T. Feder and R. Motwani, Incremental clustering and dynamic information retrieval, SIAM Journal on Computing, 33 (2004), 1417-1440. doi: 10.1137/S0097539702418498.
[4]	S. Chaudhuri, N. Garg and R. Ravi, The p-neighbor k-center problem, Information Processing Letters, 65 (1998), 131-134. doi: 10.1016/S0020-0190(97)00224-X.
[5]	S. Chechik and D. Peleg, The fault-tolerant capacitated k-center problem, Theoretical Computer Science, 566 (2015), 12-25. doi: 10.1016/j.tcs.2014.11.017.
[6]	M. Cygan, M. T. Hajiaghayi and S. Khuller, LP rounding for k-centers with non-uniform hard capacities, Proceedings of the fifity-third Annual Symposium on Foundations of Computer Science (FOCS). IEEE, (2012), 273–282.
[7]	S. B. David, A. Borodin, R. Karp, G. Tardos and A. Wigderson, On the power of randomization in on-line algorithms, Algorithmica, 11 (1994), 2-14. doi: 10.1007/BF01294260.
[8]	T. Feder and D. Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth Annual ACM Symposium on Theory of Computing, ACM, (1988), 434–444. doi: 10.1145/62212.62255.
[9]	C. G. Fernandes, S. P. de Paula and L. L. C. Pedrosa, Improved approximation algorithms for capacitated fault-tolerant k-center, Algorithmica, 80 (2018), 1041-1072.
[10]	T. F. Gonzalez, Clustering to minimize the maximum intercluster distance, Theoretical Computer Science, 38 (1985), 293-306. doi: 10.1016/0304-3975(85)90224-5.
[11]	D. S. Hochbaum and D. B. Shmoys, A best possible heuristic for the k-center problem, Mathematics of Operations Research, 10 (1985), 180-184. doi: 10.1287/moor.10.2.180.
[12]	W. L. Hsu and G. L. Nemhauser, Easy and hard bottleneck location problems, Discrete Applied Mathematics, 1 (1979), 209-215. doi: 10.1016/0166-218X(79)90044-1.
[13]	S. Khuller, R. Pless and Y. J. Sussmann, Fault tolerant k-center problems, Theoretical Computer Science, 242 (2000), 237-245. doi: 10.1016/S0304-3975(98)00222-9.
[14]	S. Khuller and Y. J. Sussmann, The capacitated k-center problem, SIAM Journal on Discrete Mathematics, 13 (2000), 403-418. doi: 10.1137/S0895480197329776.
[15]	S. O. Krumke, On a generalization of the p-center problem, Information Processing Letters, 56 (1995), 67-71. doi: 10.1016/0020-0190(95)00141-X.
[16]	E. Liberty, R. Sriharsha and M. Sviridenko, An algorithm for online k-means clustering, Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX), Society for Industrial and Applied Mathematics, (2016), 81–89. doi: 10.1137/1.9781611974317.7.
[17]	R. G. Michael and S. J. David, Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman, San Francisco, (1979), 90-91.