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)


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:
IITH CreatorsORCiD
Panolan, Fahadhttps://orcid.org/0000-0001-6213-8687
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Affine subspaces; Approximate solution; Data objects; Data points; Incomplete data; K cluster; K-means
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Mrs Haseena VKKM
Date Deposited: 25 Jan 2022 08:54
Last Modified: 11 Mar 2022 05:37
URI: http://raiith.iith.ac.in/id/eprint/9133
Publisher URL: https://epubs.siam.org/doi/10.1137/1.9781611976465...
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9133 Statistics for this ePrint Item