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

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

运筹学学报 ›› 2022, Vol. 26 ›› Issue (3): 143-150.doi: 10.15960/j.cnki.issn.1007-6093.2022.03.011

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

代宇波¹, 段懿红¹, 刘龙城¹^,*(), 王子豪¹

1. 厦门大学数学科学学院, 福建厦门 361005

收稿日期:2022-01-10 出版日期:2022-09-15 发布日期:2022-09-07
通讯作者: 刘龙城 E-mail:longchengliu@xmu.edu.cn
作者简介:刘龙城, E-mail: longchengliu@xmu.edu.cn
基金资助:
国家自然科学基金(12171402);福建省自然科学基金(2021J01031);中央高校基本科研业务费(20720220041)

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

Yubo DAI¹, Yihong DUAN¹, Longcheng LIU¹^,*(), Zihao WANG¹

1. School of Mathematical Sciences, Xiamen University, Xiamen 361005, Fujian, China

Received:2022-01-10 Online:2022-09-15 Published:2022-09-07
Contact: Longcheng LIU E-mail:longchengliu@xmu.edu.cn

摘要/Abstract

摘要：

在给定的度量空间中, 单位聚类问题就是寻找最少的单位球来覆盖给定的所有点。这是一个众所周知的组合优化问题, 其在线版本为: 给定一个度量空间, 其中的n个点会一个接一个的到达任何可能的位置, 在点到达的时候必须给该点分配一个单位聚类, 而此时未来点的相关信息都是未知的, 问题的目标是最后使用的单位聚类数目最少。本文考虑的是带如下假设的一类一维在线单位聚类问题: 在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5。本文首先给出了两个在线算法和一些引理, 接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法, 最后证明了这个组合随机算法的期望竞争比不超过1.5。

关键词: 单位聚类问题, 在线算法, 随机算法, 竞争比

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

中图分类号:

O224

代宇波, 段懿红, 刘龙城, 王子豪. 一类一维在线单位聚类问题的随机近似算法[J]. 运筹学学报, 2022, 26(3): 143-150.

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.

参考文献 10

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]	李文杰, 李钰晶, 刘海玲. 工件的释放时间和加工时间具有一致性的单机在线排序问题研究[J]. 运筹学学报, 2022, 26(2): 55-63.
[2]	王银玲, 韩鑫, 邵欣欣. 关于带运输的单机调度在线问题的研究[J]. 运筹学学报, 2022, 26(1): 125-133.
[3]	王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.
[4]	姜晓燕, 帅天平. 两台恒速机上的MapReduce排序算法研究[J]. 运筹学学报, 2020, 24(3): 57-66.
[5]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[6]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[7]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[8]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[9]	李英, 乔龙亮, 郑斐峰. 具有预知信息的集装箱码头泊位与岸桥联合调度在线模型[J]. 运筹学学报, 2018, 22(3): 28-36.
[10]	闵啸，朱俊蕾，刘静. 两台带服务等级的可拒绝同型机排序问题的在线算法[J]. 运筹学学报, 2018, 22(3): 117-124.
[11]	侯丽英. 具有服务等级的两台同型机实时在线排序[J]. 运筹学学报, 2016, 20(2): 49-58.
[12]	王成飞, 张玉忠. 提前预知信息的在线分批排序问题[J]. 运筹学学报, 2016, 20(1): 84-90.
[13]	李文华, 柴幸, 袁航, 杨素芳. 平行机上带有前瞻区间的不相容工件组在线排序问题[J]. 运筹学学报, 2015, 19(4): 121-126.
[14]	高强, 鲁习文. 带有拒绝的单机和同型机排序问题[J]. 运筹学学报, 2014, 18(4): 1-10.
[15]	姚然, 陈光亭, 张安, 陈永. 具有等级约束的三台机排序问题的可中断在线算法[J]. 运筹学学报, 2013, 17(4): 63-68.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 10

相关文章 15

编辑推荐

Metrics

本文评价