EPTAS for k-means Clustering of Affine Subspaces

We consider a generalization of the fundamental k-means clustering for data with incomplete or corrupted entries. When data objects are represented by points in R d , a data point is said to be incomplete when some of its entries are missing or unspecified. An incomplete data point with at most ∆ unspecified entries corresponds to an axis-parallel affine subspace of dimension at most ∆, called a ∆-point. Thus we seek a partition of n input ∆-points into k clusters minimizing the k-means objective. For ∆ = 0, when all coordinates of each point are specified, this is the usual k-means clustering. We give an algorithm that finds an (1 + ε)-approximate solution in time f (k, ε, ∆) • n 2 • d for some function f of k, ε, and ∆ only.