A fast approximation scheme for low-dimensional k-means

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Standard

A fast approximation scheme for low-dimensional k-means. / Cohen-Addad, Vincent.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . ed. / Artur Czumaj. Society for Industrial and Applied Mathematics, 2018. p. 430-440.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Harvard

Cohen-Addad, V 2018, A fast approximation scheme for low-dimensional k-means. in A Czumaj (ed.), Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . Society for Industrial and Applied Mathematics, pp. 430-440, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, United States, 07/01/2018. https://doi.org/10.1137/1.9781611975031.29

APA

Cohen-Addad, V. (2018). A fast approximation scheme for low-dimensional k-means. In A. Czumaj (Ed.), Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 430-440). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975031.29

Vancouver

Cohen-Addad V. A fast approximation scheme for low-dimensional k-means. In Czumaj A, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . Society for Industrial and Applied Mathematics. 2018. p. 430-440 https://doi.org/10.1137/1.9781611975031.29

Author

Cohen-Addad, Vincent. / A fast approximation scheme for low-dimensional k-means. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . editor / Artur Czumaj. Society for Industrial and Applied Mathematics, 2018. pp. 430-440

Bibtex

@inproceedings{4df30b621d464ab0ab9b29c29e832648,
title = "A fast approximation scheme for low-dimensional k-means",
abstract = "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.",
author = "Vincent Cohen-Addad",
year = "2018",
doi = "10.1137/1.9781611975031.29",
language = "English",
pages = "430--440",
editor = "Czumaj, {Artur }",
booktitle = "Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Society for Industrial and Applied Mathematics",
address = "United States",
note = "29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 ; Conference date: 07-01-2018 Through 10-01-2018",

}

RIS

TY - GEN

T1 - A fast approximation scheme for low-dimensional k-means

AU - Cohen-Addad, Vincent

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85045538879&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.29

DO - 10.1137/1.9781611975031.29

M3 - Article in proceedings

AN - SCOPUS:85045538879

SP - 430

EP - 440

BT - Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Czumaj, Artur

PB - Society for Industrial and Applied Mathematics

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

Y2 - 7 January 2018 through 10 January 2018

ER -

ID: 203834632