A Local Search Approximation Algorithm for the k-means Problem with Penalties

In this paper, we study the k-means problem with (nonuniform) penalties (k-MPWP) which is a natural generalization of the classic k-means problem. In the k-MPWP, we are given an n-client set D subset of R-d, a penalty cost p(j) > 0 for each j is an element of D, and an integer k <= n. The goal is to open a center subset F subset of R-d with vertical bar F vertical bar <= k and to choose a client subset P subset of D as the penalized client set such that the total cost (including the sum of squares of distance for each client in D \ P to the nearest open center and the sum of penalty cost for each client in P) is minimized. We offer a local search (81 + epsilon)-approximation algorithm for the k-MPWP by using single-swap operation. We further improve the above approximation ratio to (25 + epsilon) by using multi-swap operation.