Advanced Search
Article Contents
Article Contents

An adaptive probabilistic algorithm for online k-center clustering

  • * Corresponding author: Dongmei Zhang

    * Corresponding author: Dongmei Zhang
Abstract Full Text(HTML) Figure(2) Related Papers Cited by
  • 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.

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


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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

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

  • [1] D. AchlioptasM. 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-IlanG. Kortsarz and D. Peleg, How to allocate network centers, Journal of Algorithms, 15 (1993), 385-415.  doi: 10.1006/jagm.1993.1047.
    [3] M. CharikarC. ChekuriT. Feder and R. Motwani, Incremental clustering and dynamic information retrieval, SIAM Journal on Computing, 33 (2004), 1417-1440.  doi: 10.1137/S0097539702418498.
    [4] S. ChaudhuriN. 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. DavidA. BorodinR. KarpG. 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. FernandesS. 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. KhullerR. 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. 
  • 加载中



Article Metrics

HTML views(1591) PDF downloads(344) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint