Local Search Approximation Algorithms for the Spherical k-Means Problem

摘要

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 ⊂ S~d with |F| ≤ k that minimizes the sum of cosine dissimilarity measure for each client in D to the nearest open center. We give a (2(4 + 7~(1/2)) + ε)-approximation algorithm for this problem using local search scheme.