典型文献
一类一维在线单位聚类问题的随机近似算法
文献摘要：
在给定的度量空间中,单位聚类问题就是寻找最少的单位球来覆盖给定的所有点.这是一个众所周知的组合优化问题,其在线版本为:给定一个度量空间,其中的n个点会一个接一个的到达任何可能的位置,在点到达的时候必须给该点分配一个单位聚类,而此时未来点的相关信息都是未知的,问题的目标是最后使用的单位聚类数目最少.本文考虑的是带如下假设的一类一维在线单位聚类问题:在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5.本文首先给出了两个在线算法和一些引理,接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法,最后证明了这个组合随机算法的期望竞争比不超过1.5.
文献关键词：
单位聚类问题;在线算法;随机算法;竞争比
中图分类号：
作者姓名：
代宇波;段懿红;刘龙城;王子豪
作者机构：
厦门大学数学科学学院,福建厦门361005
文献出处：
引用格式：
[1]代宇波;段懿红;刘龙城;王子豪-.一类一维在线单位聚类问题的随机近似算法)[J].运筹学学报,2022(03):143-150
A类：
单位聚类问题
B类：
随机近似,近似算法,度量空间,单位球,有点,众所周知,组合优化问题,在线版,个度,来点,聚类数,离线,最优解,在线算法,引理,一个组,随机算法,竞争比
AB值：
0.327351
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
