计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2008年
10期
103-104,112
,共3页
近似算法%聚类%核心集%覆盖%最小球
近似算法%聚類%覈心集%覆蓋%最小毬
근사산법%취류%핵심집%복개%최소구
本文提出了高维空间球体的k-中心聚类问题.该问题是指对高维空间中多个球构成的集合B,构造k个球来共同覆盖B中所有已知的球,并使k个球中的最大半径最小.本文从B中有选择地取出一部分球构成集合S,称其为B的核心集,并利用该核心集,对给定ε给出了高雏空间球体k-中心聚类问题关于球数n和维数d的多项式时间1+ε近似算法.而且,S中球的个数为O(1/ε2),与B中球的个数和空间维数无关.
本文提齣瞭高維空間毬體的k-中心聚類問題.該問題是指對高維空間中多箇毬構成的集閤B,構造k箇毬來共同覆蓋B中所有已知的毬,併使k箇毬中的最大半徑最小.本文從B中有選擇地取齣一部分毬構成集閤S,稱其為B的覈心集,併利用該覈心集,對給定ε給齣瞭高雛空間毬體k-中心聚類問題關于毬數n和維數d的多項式時間1+ε近似算法.而且,S中毬的箇數為O(1/ε2),與B中毬的箇數和空間維數無關.
본문제출료고유공간구체적k-중심취류문제.해문제시지대고유공간중다개구구성적집합B,구조k개구래공동복개B중소유이지적구,병사k개구중적최대반경최소.본문종B중유선택지취출일부분구구성집합S,칭기위B적핵심집,병이용해핵심집,대급정ε급출료고추공간구체k-중심취류문제관우구수n화유수d적다항식시간1+ε근사산법.이차,S중구적개수위O(1/ε2),여B중구적개수화공간유수무관.
