# American Institute of Mathematical Sciences

• 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

 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 2019 Early access  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.

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:

show all references

##### References:
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
An illustration of partition of $S^*_i$ for any given $i\in[k]$
 [1] Baolan Yuan, Wanjun Zhang, Yubo Yuan. A Max-Min clustering method for $k$-means algorithm of data clustering. Journal of Industrial & Management Optimization, 2012, 8 (3) : 565-575. doi: 10.3934/jimo.2012.8.565 [2] Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems & Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025 [3] Gurkan Ozturk, Mehmet Tahir Ciftci. Clustering based polyhedral conic functions algorithm in classification. Journal of Industrial & Management Optimization, 2015, 11 (3) : 921-932. doi: 10.3934/jimo.2015.11.921 [4] Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial & Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185 [5] Guojun Gan, Kun Chen. A soft subspace clustering algorithm with log-transformed distances. Big Data & Information Analytics, 2016, 1 (1) : 93-109. doi: 10.3934/bdia.2016.1.93 [6] Jiangchuan Fan, Xinyu Guo, Jianjun Du, Weiliang Wen, Xianju Lu, Brahmani Louiza. Analysis of the clustering fusion algorithm for multi-band color image. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1233-1249. doi: 10.3934/dcdss.2019085 [7] Aude Hofleitner, Tarek Rabbani, Mohammad Rafiee, Laurent El Ghaoui, Alex Bayen. Learning and estimation applications of an online homotopy algorithm for a generalization of the LASSO. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 503-523. doi: 10.3934/dcdss.2014.7.503 [8] Zongwei Chen. An online-decision algorithm for the multi-period bank clearing problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021091 [9] Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems & Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022 [10] Xavier Gràcia, Xavier Rivas, Narciso Román-Roy. Constraint algorithm for singular field theories in the k-cosymplectic framework. Journal of Geometric Mechanics, 2020, 12 (1) : 1-23. doi: 10.3934/jgm.2020002 [11] Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 [12] Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269 [13] Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057 [14] Jie Shen, Jian Lv, Fang-Fang Guo, Ya-Li Gao, Rui Zhao. A new proximal chebychev center cutting plane algorithm for nonsmooth optimization and its convergence. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1143-1155. doi: 10.3934/jimo.2018003 [15] 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 [16] Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang. The approximation algorithm based on seeding method for functional $k$-means problem†. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020160 [17] Chenchen Wu, Wei Lv, Yujie Wang, Dachuan Xu. Approximation algorithm for spherical $k$-means problem with penalty. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021067 [18] Xavier Gràcia, Xavier Rivas, Narciso Román-Roy. Erratum: Constraint algorithm for singular field theories in the $k$-cosymplectic framework. Journal of Geometric Mechanics, 2021, 13 (2) : 273-275. doi: 10.3934/jgm.2021007 [19] Burak Ordin, Adil Bagirov, Ehsan Mohebi. An incremental nonsmooth optimization algorithm for clustering using $L_1$ and $L_\infty$ norms. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2757-2779. doi: 10.3934/jimo.2019079 [20] Fan Yuan, Dachuan Xu, Donglei Du, Min Li. An exact algorithm for stable instances of the $k$-means problem with penalties in fixed-dimensional Euclidean space. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021122

2020 Impact Factor: 1.801