论文部分内容阅读
本文提出了高维空间球体的k-中心聚类问题。该问题是指对高维空间中多个球构成的集合B，构造是个球来共同覆盖B中所有已知的球，并使k个球中的最大半径最小。本文从B中有选择地取出一部分球构成集合s，称其为B的核心集，并利用该核心集，对给定ε给出了高维空间球体k-中心聚类问题关于球数n和维数d的多项式时间1-ε近似算法。而且，S中球的个数为O（1／ε^2），与B中球的个数和空间维数无关。