On Parallel 𝑘 -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 \ (O (n^) \), where \ ( (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 \ ( (k) \) or even \ ( (kn^) \) 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 (n^) \), has been considered recently for the low-local-space MPC model by Bateni et al. (2021), who gave an \ (O (n) \) -round MPC algorithm that produces \ (k (1+o (1) ) \) centers whose cost has multiplicative approximation of \ (O (n) \). In this paper we extend the algorithm of Bateni et al. and design a low-local-space MPC algorithm that in \ (O (n) \) rounds returns a clustering with \ (k (1+o (1) ) \) clusters that is an \ (O (^*n) \) -approximation for \ (k\) -center.