An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the \(k\)-Means Problem

In this paper, we present an efficient massively parallel approximation algorithm for the \(k\)-means problem. Specifically, we provide an MPC algorithm that computes a constant-factor approximation to an arbitrary \(k\)-means instance in \(O(\log \log n \cdot \log \log \log n)\) rounds. The algorithm uses \(O(n^{\sigma})\) bits of memory per machine, where \(\sigma \gt 0\) is a constant that can be made arbitrarily small. The global memory usage is \(O(n^{1+\varepsilon})\) bits for an arbitrarily small constant \(\varepsilon \gt 0\), and is thus only slightly superlinear. Recently, Czumaj, Gao, Jiang, Krauthgamer, and Veselý showed that a constant-factor bicriteria approximation can be computed in \(O(1)\) rounds in the MPC model. However, our algorithm is the first constant-factor approximation for the general \(k\)-means problem that runs in \(o(\log n)\) rounds in the MPC model.