Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces
- Title
- Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces
- Authors
- Cho, Kyungjin; OH, EUNJIN
- Date Issued
- 2021-12-07
- Publisher
- Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
- Abstract
- In this paper, we present a linear-time approximation scheme for k-means clustering of incomplete data points in d-dimensional Euclidean space. An incomplete data point with ∆ > 0 unspecified entries is represented as an axis-parallel affine subspace of dimension ∆. The distance between two incomplete data points is defined as the Euclidean distance between two closest points in the axis-parallel affine subspaces corresponding to the data points. We present an algorithm for k-means clustering of axis-parallel affine subspaces of dimension ∆ that yields an (1 + ϵ)-approximate solution in O(nd) time. The constants hidden behind O(·) depend only on ∆, ϵ and k. This improves the O(n
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/110014
- Article Type
- Conference
- Citation
- 32nd International Symposium on Algorithms and Computation, ISAAC 2021, 2021-12-07
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.