Local search approximation algorithms 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 $$ {\mathcal {D}} \subset {\mathbb {R}}^d$$ D ⊂ R d , a penalty cost $$p_j>0$$ p j > 0 for each $$j \in {\mathcal {D}}$$ j ∈ D , and an integer $$k \le n$$ k ≤ n . The goal is to open a center subset $$F \subset {\mathbb {R}}^d$$ F ⊂ R d with $$ |F| \le k$$ | F | ≤ k and to choose a client subset $$P \subseteq {\mathcal {D}} $$ P ⊆ D as the penalized client set such that the total cost (including the sum of squares of distance for each client in $$ {\mathcal {D}} \backslash P $$ 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+ \varepsilon )$$ ( 81 + ε ) -approximation algorithm for the k-MPWP by using single-swap operation. We further improve the above approximation ratio to $$( 25+ \varepsilon )$$ ( 25 + ε ) by using multi-swap operation.