收录:
摘要:
In this paper, we study the spherical k-means problem (SKMP) which is one of the most well-studied clustering problems. In the SKMP, we are given an n-client set D in d-dimensional unit sphere S-d, and an integer k <= n. The goal is to open a center subset F subset of S-d with vertical bar F vertical bar <= k that minimizes the sum of cosine dissimilarity measure for each client in D to the nearest open center. We give a (2(4 + root 7) + epsilon)-approximation algorithm for this problem using local search scheme.
关键词:
通讯作者信息:
电子邮件地址: