A Simple D 2-Sampling Based PTAS for k-Means and Other Clustering Problems
Given a set of points \(P \subset\mathbb{R}^{d}\), the k-means clustering problem is to find a set of k centers \(C = \{ c_{1},\ldots,c_{k}\}, c_{i} \in\mathbb{R}^{d}\), such that the objective function ? x?P e(x,C)2, where e(x,C) denotes the Euclidean distance between x and the closest center in C, is minimized. This is one of the most prominent objective functions that has been studied with respect to clustering.
ptas k-means clustering sampling k-median