American Institute of Mathematical Sciences

Advanced
  • Previous Article
    An uncertain programming model for single machine scheduling problem with batch delivery
  • JIMO Home
  • This Issue
  • Next Article
    RETRACTION: Peng Zhang, Chance-constrained multiperiod mean absolute deviation uncertain portfolio selection
April  2019, 15(2): 565-576. doi: 10.3934/jimo.2018057

An adaptive probabilistic algorithm for online k-center clustering

Ruiqi Yang 1, , Dachuan Xu 1, , Yicheng Xu 1, and  Dongmei Zhang 2,,

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

Received  August 2017 Revised  December 2017 Published  April 2018

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: k-center, online clustering, probabilistic algorithm.
Mathematics Subject Classification: Primary: 90C27; Secondary: 68W27.
Citation: Ruiqi Yang, Dachuan Xu, Yicheng Xu, Dongmei Zhang. An adaptive probabilistic algorithm for online k-center clustering. Journal of Industrial & Management Optimization, 2019, 15 (2) : 565-576. doi: 10.3934/jimo.2018057
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

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 Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

[1]

Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056
[2]

Antonio Rieser. A topological approach to spectral clustering. Foundations of Data Science, 2021, 3 (1) : 49-66. doi: 10.3934/fods.2021005
[3]

Takeshi Saito, Kazuyuki Yagasaki. Chebyshev spectral methods for computing center manifolds. Journal of Computational Dynamics, 2021  doi: 10.3934/jcd.2021008
[4]

Yohei Yamazaki. Center stable manifolds around line solitary waves of the Zakharov–Kuznetsov equation with critical speed. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3579-3614. doi: 10.3934/dcds.2021008
[5]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[6]

Wei Wang, Yang Shen, Linyi Qian, Zhixin Yang. Hedging strategy for unit-linked life insurance contracts with self-exciting jump clustering. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021072
[7]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781
[8]

Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044
[9]

Ka Luen Cheung, Man Chun Leung. Asymptotic behavior of positive solutions of the equation $ \Delta u + K u^{\frac{n+2}{n-2}} = 0$ in $IR^n$ and positive scalar curvature. Conference Publications, 2001, 2001 (Special) : 109-120. doi: 10.3934/proc.2001.2001.109
[10]

Tadeusz Kaczorek, Andrzej Ruszewski. Analysis of the fractional descriptor discrete-time linear systems by the use of the shuffle algorithm. Journal of Computational Dynamics, 2021  doi: 10.3934/jcd.2021007
[11]

Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045
[12]

Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066
[13]

Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063
[14]

Grace Nnennaya Ogwo, Chinedu Izuchukwu, Oluwatosin Temitope Mewomo. A modified extragradient algorithm for a certain class of split pseudo-monotone variational inequality problem. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021011

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (191)
  • HTML views (1120)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences