On Parallel <i>𝑘</i> -Center Clustering

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