DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cho, Kyungjin | - |
dc.contributor.author | OH, EUNJIN | - |
dc.date.accessioned | 2022-03-02T05:40:40Z | - |
dc.date.available | 2022-03-02T05:40:40Z | - |
dc.date.created | 2022-03-02 | - |
dc.date.issued | 2021-12-07 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/110014 | - |
dc.description.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 | - |
dc.language | English | - |
dc.publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing | - |
dc.relation.isPartOf | 32nd International Symposium on Algorithms and Computation, ISAAC 2021 | - |
dc.relation.isPartOf | Leibniz International Proceedings in Informatics, LIPIcs | - |
dc.title | Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces | - |
dc.type | Conference | - |
dc.type.rims | CONF | - |
dc.identifier.bibliographicCitation | 32nd International Symposium on Algorithms and Computation, ISAAC 2021 | - |
dc.citation.conferenceDate | 2021-12-06 | - |
dc.citation.conferencePlace | JA | - |
dc.citation.conferencePlace | online | - |
dc.citation.title | 32nd International Symposium on Algorithms and Computation, ISAAC 2021 | - |
dc.contributor.affiliatedAuthor | Cho, Kyungjin | - |
dc.contributor.affiliatedAuthor | OH, EUNJIN | - |
dc.identifier.scopusid | 2-s2.0-85122432228 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.