EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On Parallel k -Center Clustering

Sam Coy, Artur Czumaj, Gopinath Mishra

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

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →