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

• 作者: 栾峻峰 范克磊 鲍海峰
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 近似算法 聚类 核心集 覆盖 最小球
• 年，卷（期）: 2008,（10）
• 所属期刊栏目: 离散数学理论与应用
• 页码范围: 103-104,112
• 页数: 3页
• 分类号: TP301.6
• 字数: 2771字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2008.10.036

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	栾峻峰	山东大学计算机科学与技术学院	12	19	3.0	3.0
2	范克磊	山东大学计算机科学与技术学院	2	3	1.0	1.0
3	鲍海峰	山东大学计算机科学与技术学院	1	3	1.0	1.0