高维空间球体的k-中心聚类问题

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

The k-Center Clustering Problem of High-Dimensional Space Balls

The paper proposes the k -center clustering problem of high-dimensional space balls. The problem means as for the set B built by the multiple bails ina high-dimensional space, k bails are built to cover all the known bails in B and make the biggest radius of the k balls the smallest. We selectively s elect some balls from B to build sets, which is called the core set of B , and for a given ε, we use the core set to propose the polynomial time 1 ＋ ε approximation algorithm with ball number n and dimension d based on the k -center clustering problem of high-dimensional space balls. And the number  of balls in S is 0 （1/ε^2 ）, which is not related to the number of balls in B and the dimension of the space.LUAN Jun-feng, FAN Ke-lei, BAO Hai-feng