Better Approximation for Distributed Data Summarization Fair $k$-Center in the MPC Model

The massively parallel computation (MPC) model provides a theoretical framework for large-scale data processing systems such as MapReduce. We study data-summarization fair $k$-center in a one-round, coordinator-based MPC model. The objective is to select at most $k$ centers from the input to minimize the maximum distance from any input point to its nearest center, subject to group upper bounds. Given $n$ points partitioned into $m$ groups and distributed across $\ell$ workers, each worker independently constructs a subset summary, from which the coordinator computes a fair solution. Our framework combines group-wise local summaries with a compact maximum-flow formulation: the summaries preserve same-group replacements for optimal centers, while geometric separation ensures flow feasibility. This yields a $(7+\epsilon )$-approximation in general metrics using at most $\min (n,\ell mk)$ transmitted point records, improving the previous approximation factor of $17$ while retaining $O(km)$ transmitted records per worker. When the optimal fair radius is known to the coordinator, refined summaries yield a $(3+\epsilon )$-approximation in metrics of bounded doubling dimension and a $(5.84+\epsilon )$-approximation in Euclidean spaces of arbitrary dimension. For one-way subset-summary protocols with only local distance access, we also establish an $\Omega (n)$ communication lower bound for approximation factors strictly below $5$ on instances with $\Theta (n)$ workers. Experiments on three real-world datasets and synthetic inputs demonstrate competitive clustering quality and practical efficiency under simulated parallel execution.