On Parallel k -Center Clustering
ACM Transactions on Algorithms · 31.07.2026 · 22 (3) · 1-29
DOI: 10.1145/3811812 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 03.06.2026. Verfasst von Sam Coy und 2 weiteren Autor:innen. Die Arbeit nennt 40 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
We consider the classic \( k \) -center problem in the constant dimensional Euclidean space under a parallel setting, on the low-local-space Massively Parallel Computation (MPC) model, with local space per machine of \(\mathcal{O}(n^{\delta})\) , where \(\delta\in(0,1)\) is an arbitrary constant. As a central clustering problem, the \( k \) -center problem has been studied extensively. Still, until very recently, all parallel MPC algorithms have been requiring \(\Omega(k)\) or even \(\Omega(kn^{\delta})\) local space per machine. While this setting covers the case of small values of \( k \) , for a large number of clusters these algorithms require large local memory, making them poorly scalable. The case of large \( k \) , \(k\geq\Omega(n^{\delta})\) , has been considered recently for the low-local-space MPC model by Bateni et al. [2021], who gave an \(\mathcal{O}(\log\log n)\) -round MPC algorithm that produces \(k(1+o(1))\) centers whose cost has multiplicative approximation of \(\mathcal{O}(\log\log\log n)\) . In this article, we extend the algorithm of Bateni et al. and design a low-local-space MPC algorithm that in \(\mathcal{O}(\log\log n)\) rounds returns a clustering with \(k(1+o(1))\) clusters that is an \(\mathcal{O}(\log^{*}n)\) -approximation for \( k \) -center.
Zitieren
APA
Coy, S., Czumaj, A., & Mishra, G. (2026). On Parallel k -Center Clustering. ACM Transactions on Algorithms, 22(3), 1-29. https://doi.org/10.1145/3811812
Vancouver
Coy S, Czumaj A, Mishra G. On Parallel k -Center Clustering. ACM Transactions on Algorithms. 2026;22(3):1-29. doi:10.1145/3811812
BibTeX
@article{Coy2026,
author = {Coy, Sam and Czumaj, Artur and Mishra, Gopinath},
title = {On Parallel k -Center Clustering},
journal = {ACM Transactions on Algorithms},
year = {2026},
volume = {22},
number = {3},
pages = {1--29},
doi = {10.1145/3811812}
}
EUVIMED