An approximation algorithm for the spherical k -means problem with outliers by local search

We consider the spherical k-means problem with outliers, an extension of the k-means problem. In this clustering problem, all sample points are on the unit sphere. Given two integers k and z, we can ignore at most z points (outliers) and need to find at most k cluster centers on the unit sphere and assign remaining points to these centers to minimize the k-means objective. It has been proved that any algorithm with a bounded approximation ratio cannot return a feasible solution for this problem. Our contribution is to present a local search bi-criteria approximation algorithm for the spherical k-means problem.