Operations Research Transactions >
2022 , Vol. 26 >Issue 3: 143 - 150
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.03.011
Randomized approximation algorithms for a class of one-dimensional online unit clustering problem
Received date: 2022-01-10
Online published: 2022-09-07
In a given metric space, the unit clustering problem is to find a minimum number of unit balls to cover all the given points. It is a well known combinatorial optimization problem and the online version is: Given a set of n points in a given metric space, which arrive one by one at any locations, the point should be assigned to a unit cluster at the time of its arrival without any future information, the goal is to minimize the number of used clusters. In this paper, we consider a class of online unit clustering problem in one dimension with the assumption that the distance between any two adjacent clusters in the offline optimal solution is greater than 0.5. We first present two online algorithms with some lemmas, and then present a combined randomized algorithm which run the two online algorithms with a probability 0.5. We show that the expected competitive ratio of the combined randomized algorithm is at most 1.5.
Yubo DAI, Yihong DUAN, Longcheng LIU, Zihao WANG . Randomized approximation algorithms for a class of one-dimensional online unit clustering problem[J]. Operations Research Transactions, 2022 , 26(3) : 143 -150 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.011
| 1 | Cormen T H , Leiserson C E , Rivest R L , et al. Introduction to Algorithms[M]. Cambridge: MIT Press, 2009. |
| 2 | Meyerson A. Online facility location[C]//Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, 2001: 426-433. |
| 3 | Charikar M , Chekuri C , Feder T , et al. Incremental clustering and dynamic information retrieval[J]. SIAM Journal on Computing, 2004, 33 (6): 1417- 1440. |
| 4 | Fotakis D . Incremental algorithms for facility location and $k$-median[J]. Theoretical Computer Science, 2006, 361, 275- 313. |
| 5 | Sleator D D , Tarjan R E . Amortized efficiency of list update and paging rules[J]. Communications of the ACM, 1985, 28 (2): 202- 208. |
| 6 | Borodin A , El-Yaniv R . Online Computation and Competitive Analysis[M]. Cambridge: Cambridge University Press, 1998. |
| 7 | Chan T M, Zarrabi-Zadeh H. A randomized algorithm for online unit clustering[C]//Proceedings of the 4th Workshop on Approximation and Online Algorithms, 2006: 121-131. |
| 8 | Zarrabi-Zadeh H , Chan T M . An improved algorithm for online unit clustering[J]. Algorithmica, 2009, 54, 490- 500. |
| 9 | Epstein L , Stee R V . On the online unit clustering problem[J]. ACM Transactions Algorithms, 2010, 7 (1): 1- 18. |
| 10 | Csirik J , Epstein L , Imreh C , et al. Onine clustering with variable sized clusters[J]. Algorithmica, 2013, 65, 251- 274. |
/
| 〈 |
|
〉 |
