New Algorithms for Distributed Fair k-Center Clustering: Almost Accurate as Sequential Algorithms

Fair clustering problems have been paid lots of attention recently. In this paper, we study the 𝑘-Center problem under the group fairness and data summarization fairness constraints, denoted as Group Fair 𝑘-Center (GF𝑘C) and Data Summarization Fair 𝑘-Center (DSF𝑘C), respectively, in the massively parallel computational (MPC) distributed model. The previous best results for the above two problems in the MPC model are a 9-approximation with violation 7 (WWW 2022) and a (17 + 𝜖)-approximation without fairness violation (ICML 2020), respectively. In this paper, we obtain a (3 + 𝜖)approximation with violation 1 for the GF𝑘C problem in the MPC model, which is almost as accurate as the best known approximation ratio 3 with violation 1 for the sequential algorithm of the GF𝑘C problem. Moreover, for the DSF𝑘C problem in the MPC model, we obtain a (4 + 𝜖)-approximation without fairness violation, which is very close to the best known approximation ratio 3 for the sequential algorithm of the DSF𝑘C problem. Empirical experiments show that our distributed algorithms perform better than existing state-of-the-art distributed methods for the above two problems.