一类一维在线单位聚类问题的随机近似算法

doi:10.15960/j.cnki.issn.1007-6093.2022.03.011

Abstract

Abstract:

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.

Key words: unit clustering problem, online algorithm, randomized algorithm, competitive ratio

CLC Number:

O224

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.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2022.03.011

https://www.ort.shu.edu.cn/EN/Y2022/V26/I3/143

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. doi: 10.1137/S0097539702418498
4	Fotakis D . Incremental algorithms for facility location and $k$-median[J]. Theoretical Computer Science, 2006, 361, 275- 313. doi: 10.1016/j.tcs.2006.05.015
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. doi: 10.1145/2786.2793
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. doi: 10.1007/s00453-008-9208-9
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. doi: 10.1007/s00453-011-9586-2

[1]	Qian XIA, Xingong ZHANG. Online scheduling problem of two flow shop with lookahead interval and incompatible job family [J]. Operations Research Transactions, 2025, 29(4): 103-111.
[2]	Kaiyuan JIN, Feifeng ZHENG, Ming LIU. Online scheduling model of batch processing machine considering order types and setup time [J]. Operations Research Transactions, 2025, 29(4): 231-240.
[3]	Na LI, Ran MA, Long LI, Yuzhong ZHANG. Study on the production scheduling of prefabricated components with learning effect [J]. Operations Research Transactions, 2025, 29(1): 19-30.
[4]	Wenjie LI, Zhihui DU, Menglong SU. Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times [J]. Operations Research Transactions, 2024, 28(4): 18-28.
[5]	Juannian XU, Ran MA, Wenwen HAN, Yuzhong ZHANG. Single-machine online scheduling to minimize maximum weighted completion time with limited weights [J]. Operations Research Transactions, 2024, 28(2): 71-80.
[6]	Wenjie LI, Yujing LI, Hailing LIU. Research on the single-machine online schedule in which the jobs' release times and processing times are agreeable [J]. Operations Research Transactions, 2022, 26(2): 55-63.
[7]	Yinling WANG, Xin HAN, Xinxin SHAO. Online single machine scheduling problem with transportation [J]. Operations Research Transactions, 2022, 26(1): 125-133.
[8]	Libo WANG, Wenhua LI, Dan YU. Online scheduling on single batch machine with variable lookahead interval [J]. Operations Research Transactions, 2022, 26(1): 134-140.
[9]	JIANG Xiaoyan, SHUAI Tianping. Online MapReduce scheduling on two uniform machines [J]. Operations Research Transactions, 2020, 24(3): 57-66.
[10]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[11]	LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao. On-line bounded-batching scheduling of unit-length jobs with two families [J]. Operations Research Transactions, 2019, 23(4): 105-110.
[12]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[13]	PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei. Online batch scheduling problem on uniform machines with agreeable processing times [J]. Operations Research Transactions, 2019, 23(1): 111-118.
[14]	MIN Xiao, ZHU Junlei, LIU Jing. An online algorithm for hierarchical scheduling on two identical machines with rejection [J]. Operations Research Transactions, 2018, 22(3): 117-124.
[15]	LI Ying, QIAO Longliang, ZHENG Feifeng. A study of online berth and quay crane integrated allocation problem with lookahead ability [J]. Operations Research Transactions, 2018, 22(3): 28-36.

Randomized approximation algorithms for a class of one-dimensional online unit clustering problem

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 15

Recommended Articles

Metrics

Comments