On Parallel k-Center Clustering

We consider the classic k-center problem in a parallel setting, on the low-local-space Massively Parallel Computation (MPC) model, with local space per machine of O(n(delta)), where delta is an element of(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 >= Omega(n(delta)), has been considered recently for the low-local-space MPC model by Bateni et al. (2021), who gave an O(log log n)-round MPC algorithm that produces k(1 + o(1)) centers whose cost has multiplicative approximation of 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 O(log log..) rounds returns a clustering with k(1 + o(1)) clusters that is an O(log*n)-approximation for k-center.