高维空间球集覆盖问题的改进1+ε近似算法
【出 处】:《
计算机工程与科学
》
CSCD
2010年第1期 44-46页,共4页
【作 者】:
范克磊
;
栾峻峰
【摘 要】
高维空间球集的覆盖问题是指对高维空间中多个球构成的集合S,构造一个直径最小的球来覆盖S中所有已知球。本文提出了球集直径的概念,给出求解球集直径的1/√3近似算法。基于此算法求解球集实例集合S的初始核心集,进而给出高维空间球集覆盖问题的1+ε近似算法,算法时间复杂度为O(nd/ε+d^2/ε^3/2(1/ε+d)lgl/ε)。算法保证核心集中球的个数为O(1/ε),与S中球的个数和空间维数无关。
相关热词搜索: