Linear-Time Approximation Scheme for k-Means Clustering of Affine Subspaces

Kyungjin Cho, Eunjin Oh

In this paper, we present a linear-time approximation scheme for $k$-means clustering of \emph{incomplete} data points in $d$-dimensional Euclidean space. An \emph{incomplete} data…