A fast approximation scheme for low-dimensional k-means
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
We consider the popular k-means problem in ddimensional Euclidean space. Recently Friggstad, Rezapour, Salavatipour [FOCS'16] and Cohen-Addad, Klein, Mathieu [FOCS'16] showed that the standard local search algorithm yields a p1"q-approximation in time pn kq1-"Opdq, giving the first polynomial-time approximation scheme for the problem in low-dimensional Euclidean space. While local search achieves optimal approximation guarantees, it is not competitive with the state-of-the-art heuristics such as the famous kmeans++ and D2-sampling algorithms. In this paper, we aim at bridging the gap between theory and practice by giving a p1 "q-approximation algorithm for low-dimensional k-means running in time nk plog nqpd" 1qOpdq, and so matching the running time of the k-means++ and D2-sampling heuristics up to polylogarithmic factors. We speed-up the local search approach by making a non-standard use of randomized dissections that allows to find the best local move efficiently using a quite simple dynamic program. We hope that our techniques could help design better local search heuristics for geometric problems.
Originalsprog | Engelsk |
---|---|
Titel | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms |
Redaktører | Artur Czumaj |
Forlag | Society for Industrial and Applied Mathematics |
Publikationsdato | 2018 |
Sider | 430-440 |
ISBN (Elektronisk) | 9781611975031 |
DOI | |
Status | Udgivet - 2018 |
Begivenhed | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, USA Varighed: 7 jan. 2018 → 10 jan. 2018 |
Konference
Konference | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 |
---|---|
Land | USA |
By | New Orleans |
Periode | 07/01/2018 → 10/01/2018 |
Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), SIAM Activity Group on Discrete Mathematics |
ID: 203834632