EPTAS for k-means clustering of affine subspaces

Eiben, E. and Panolan, F. (2021) EPTAS for k-means clustering of affine subspaces. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 10 January 2021 through 13 January 2021, Alexandria, Virtual.

Full text not available from this repository. (Request a copy)

Abstract

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 ℝ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, ∊, Δ) · n2 · d for some function f of k, ∊, and Δ only. © 2021 by SIAM

[error in script]

IITH Creators: