关键词: 近似算法 聚类 核心集 覆盖 最小球

Abstract:

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

Key words: approximation algorithm, clustering, core-set, covering, smallest ball