Extreme K-Center Clustering

MohammadHossein Bateni, Hossein Esfandiari, Manuela Fischer, Vahab S. Mirrokni

AAAI 2021 pp. 3941-3949

doi:10.1609/AAAI.V35I5.16513 /aaai/2021/bateni2021aaai-extreme/

Abstract

Metric clustering is a fundamental primitive in machine learning with several applications for mining massive datasets. An important example of metric clustering is the k-center problem. While this problem has been extensively studied in distributed settings, all previous algorithms use Ω(k) space per machine and Ω(n k) total work. In this paper, we develop the first highly scalable approximation algorithm for k-center clustering, with O~(n^ε) space per machine and O~(n^(1+ε)) total work, for arbitrary small constant ε. It produces an O(log log log n)-approximate solution with k(1+o(1)) centers in O(log log n) rounds of computation.

PDF AAAI Semantic Scholar

Cite

Text

Bateni et al. "Extreme K-Center Clustering." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I5.16513

Markdown

[Bateni et al. "Extreme K-Center Clustering." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/bateni2021aaai-extreme/) doi:10.1609/AAAI.V35I5.16513

BibTeX

@inproceedings{bateni2021aaai-extreme,
  title     = {{Extreme K-Center Clustering}},
  author    = {Bateni, MohammadHossein and Esfandiari, Hossein and Fischer, Manuela and Mirrokni, Vahab S.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2021},
  pages     = {3941-3949},
  doi       = {10.1609/AAAI.V35I5.16513},
  url       = {https://mlanthology.org/aaai/2021/bateni2021aaai-extreme/}
}