Local search yields a PTAS for fixed-dimensional k-means problem with penalties

We study a problem called the k-means problem with penalties (k-MPWP), which is a natural generalization of the typical k-means problem. In this problem, we have a set D of client points in R-d, a set F of possible centers in R-d, and a penalty cost p(j) > 0 for each point j is an element of D. We are also given an integer k which is the size of the center point set. We want to find a center point set S subset of F with size k, choose a penalized subset of clients P subset of D, and assign every client in D\P to its open center. Our goal is to minimize the sum of the squared distances between every point in D\P to its assigned centre point and the sum of the penalty costs for all clients in P. By using the multi-swap local search technique and under the fixed-dimensional Euclidean space setting, we present a polynomial-time approximation scheme (PTAS) for the k-MPWP.

Automated summary

This article studies a natural generalization of the typical k-means problem, called the k-means problem with penalties (k-MPWP), and presents a polynomial-time approximation scheme (PTAS) for this problem using the multi-swap local search technique.