高维空间球集覆盖问题的改进1+ε近似算法

doi:10.3969/j.issn.1007130X.2010.

J4 ›› 2010, Vol. 32 ›› Issue (1): 44-46.doi: 10.3969/j.issn.1007130X.2010.

高维空间球集覆盖问题的改进1+ε近似算法

（山东大学计算机科学与技术学院，山东济南 250101）

收稿日期:2009-04-12 修回日期:2009-07-10 出版日期:2010-01-18 发布日期:2010-01-18
通讯作者: 250101 山东省济南市山东大学计算机科学与技术学院 E-mail:foreverfkl@qq.com
作者简介:范克磊（1985-），男，山东潍坊人，硕士生，研究方向为算法分析与设计；栾峻峰，副教授，研究方向为算法分析与设计。

Improved 1+ε Approximation Algorithms forthe Balls in High Dimensions via CoreSets

（School of Computer Science and Technology,Shandong University,Jinan 250101,China）

Received:2009-04-12 Revised:2009-07-10 Online:2010-01-18 Published:2010-01-18

摘要/Abstract

摘要：

高维空间球集的覆盖问题是指对高维空间中多个球构成的集合S，构造一个直径最小的球来覆盖S中所有已知球。本文提出了球集直径的概念，给出求解球集直径的1/〖KF(〗3〖KF)〗近似算法。基于此算法求解球集实例集合S的初始核心集，进而给出高维空间球集覆盖问题的1+ε近似算法，算法时间复杂度为O(nd/ε+d2/ε〖SX(〗3〖〗2〖SX)〗(1/ε+d)lg1/ε)。算法保证核心集中球的个数为 O(1/ε)，与S中球的个数和空间维数无关。

关键词: 最小覆盖球, 核心集, 高维空间球集, 近似算法, 计算几何

Abstract:

The minimum enclosing ball problem means to construct a ball of the minimum radius enclosing a given set of balls in 〖WTBX〗S〖WTBZ〗.We propose the concept of the diameter of a set of balls and give an approximation algorithm solve the diameter. We developthe 1+ε approximation algorithm using coresets. The time complexity of this algorithm is O(nd/ε+d2/ε〖SX(〗32〖SX)〗(1/ε+d)log(1/ε)). We prove the existence of the coresets of size O(1/ε) are unrelated to n and d.

Key words: minimum enclosing ball;coreset;balls in high dimensions;approximation algorithm;computational geometry

中图分类号:

TP301.6

范克磊, 栾峻峰. 高维空间球集覆盖问题的改进1+ε近似算法[J]. J4, 2010, 32(1): 44-46.

FAN Ke-Lei, LUAN Jun-Feng. Improved 1+ε Approximation Algorithms forthe Balls in High Dimensions via CoreSets[J]. J4, 2010, 32(1): 44-46.

[1]	钟昊, 陈卫东. 一般图中的最小概要表示集问题[J]. 计算机工程与科学, 2023, 45(01): 113-118.
[2]	包敏泽, 胡秀婷, 谢玉莹, 蒋波. 基于人工蜂群算法的p-center问题求解算法[J]. 计算机工程与科学, 2020, 42(06): 1127-1133.
[3]	关莉，冯彦雪. 混合环上带惩罚费用的负载平衡问题[J]. 计算机工程与科学, 2019, 41(11): 1949-1953.
[4]	程佳乐，李伟东. 具有树和路约束的平行机排序问题[J]. 计算机工程与科学, 2018, 40(12): 2273-2279.
[5]	樊广佺1，马丽平2. 一种改进的基于Delaunay三角网的聚类算法[J]. J4, 2016, 38(03): 585-589.
[6]	颜庆，张鹏. 社会网络中的影响力最大化问题[J]. J4, 2015, 37(02): 263-268.
[7]	王敏，吴中博，徐德刚，屈俊峰，吴钊. 基于预测模型的传感器网络近似数据采集算法[J]. J4, 2014, 36(11): 2148-2152.
[8]	刘玉堂，方奇志. 限制设施选址问题的近似算法[J]. J4, 2013, 35(4): 111-114.
[9]	杨宪泽,肖明. 一种混合式机器翻译方法的分析研究[J]. J4, 2012, 34(2): 168-171.
[10]	王刚，骆志刚，李聪，黄旭慧. 近似算法之测度视角[J]. J4, 2012, 34(11): 83-90.
[11]	幸冬梅[1,2]. 一类弱支配集问题的近似算法[J]. J4, 2008, 30(12): 97-101.
[12]	丁玲玲方奇志. 控制集与部分控制集问题的原始-对偶算法[J]. J4, 2008, 30(12): 102-104.
[13]	唐晋韬王挺. 复杂社会网络的介数性质近似计算方法研究[J]. J4, 2008, 30(12): 9-14.
[14]	伍勇安殷建平李敏. 无线传感器网络连通忌覆盖问题及其解决方案综述[J]. J4, 2008, 30(11): 155-158.
[15]	栾峻峰范克磊鲍海峰. 高维空间球体的k-中心聚类问题[J]. J4, 2008, 30(10): 103-104.

高维空间球集覆盖问题的改进1+ε近似算法

Improved 1+ε Approximation Algorithms forthe Balls in High Dimensions via CoreSets

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价