Eiben, E. and Panolan, F.
(2021)
EPTAS for kmeans clustering of affine subspaces.
In: Proceedings of the Annual ACMSIAM 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 kmeans 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 axisparallel affine subspace of dimension at most Δ, called a Δpoint. Thus we seek a partition of n input Δpoints into k clusters minimizing the kmeans objective. For Δ = 0, when all coordinates of each point are specified, this is the usual kmeans 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]
Actions (login required)

View Item 