acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

The massively parallel computation (MPC) model provides a theoretical framework for large-scale data processing systems such as MapReduce. We study data-summarization fair -center in a one-round, coordinator-based MPC model. The objective is to select at most centers from the input to minimize the maximum distance from any input point to its nearest center, subject to group upper bounds. Given points partitioned into groups and distributed across 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 -approximation in general metrics using at most transmitted point records, improving the previous approximation factor of while retaining transmitted records per worker. When the optimal fair radius is known to the coordinator, refined summaries yield a -approximation in metrics of bounded doubling dimension and a -approximation in Euclidean spaces of arbitrary dimension. For one-way subset-summary protocols with only local distance access, we also establish an communication lower bound for approximation factors strictly below on instances with workers. Experiments on three real-world datasets and synthetic inputs demonstrate competitive clustering quality and practical efficiency under simulated parallel execution.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Clustering, massive parallel computation, fairness

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_E8SeOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper gives algorithms for fair k-center clustering in the one-round coordinator-based MPC model. Specifically, the problem studied has input PP, partitioned in two ways: mm disjoint groups (P=⋃j=1mGjP = \bigcup_{j=1}^m G_j) and ℓ\ell workers (P=⋃i=1ℓPiP = \bigcup_{i=1}^{\ell} P_i), each group has a specified number of centers kjk_j allowed. The objective is to minimize the maximum distance of points in the set to the nearest center. The algorithms do the following: Each worker submits candidate points from their partition to the coordinator, then the coordinator takes a net of the candidates (using the known optimal cluster radius) and computes the final result using integer max flow. Let worker partions be P=P1∪⋯∪PℓP = P_1 \cup \dots \cup P_\ell. Results include 3 regimes:

  • A 7-approximation in general metrics; O(kml)O(kml) points communication; O(m+k∣Pi∣)O(m + k|P_i|) work per partition; O(knΦ+k2m)O(kn_\Phi + k^2m) coordinator work, where nΦn_\Phi is the size of the summaries received by the workers. This is an improvement from the previous 17-approximation result with the same communication bound.
  • In doubling dimension DD, and ε∈(0,1]\varepsilon \in (0,1], a (3+ε)(3 + \varepsilon)-approximation and min⁡{n,lmk(32/ε)D}\min\{n, lmk(32/\varepsilon)^D\} points communication. This inproves the approximation from (4+ε)(4 + \varepsilon) in prior work while increasing communication by a factor of 8D8^D.
  • In Euclidean spaces a 5.84-approximation using min⁡{n,122lmk}\min\{n,122lmk\} points communication.

The authors also give a 5-approximation lower bound for Θ(n)\Theta(n) workers (any lower factor requires Ω(n)\Omega(n) points communication). They also give some experimental evaluation using simulated parallel execution.

Critical strengths

The fair k-center algorithms are simple and the analysis is clear/easy to follow. I like that the same algorithmic idea is used in the three regimes. In my opinion that makes it a stronger contribution than if each regime had more specific technical machinery. Reducing the approximation from 17 to 7 for general metrics while keeping communication the same seems like a meaningful contribution. I lean towards acceptance because I think the techniques/framework can be easily appreciated.

Critical weaknesses

The paper could have done a better job characterizing the tradeoffs introduced by the parameters and dimension. The results for general metric, doubling metric, and Euclidean have different tradeoffs on dimension, epsilon, communication, and coordinator work, but little guidance is given as to when a regime is preferred. (And it is also not addressed experimentally. For example, what about in a high-dimensional Euclidean space with data that is intrinsically low dimensional?) Less important, but although correct, the communication lower bound doesn't seem as significant because it requires Θ(n)\Theta(n) workers. The paper should also compare this result to existing lower bounds.

Questions for authors
  • For the Euclidean regime, is the 5.84-approximation the first dimension-independent constant-factor guarantee for this model? Or is this a constant factor improvement from prior work?

  • Worker computation, approximation, and communication are discussed, but for the doubling metric and Euclidean regime, can you discuss the comparison of the coordinator work in your algorithms to prior work?

  • In the results section, it's unclear what is meant by running time. Is this only the coordinator? Or is this worker/coordinator both? Or how should I interpret the results?

  • Some of the complexity results are stated in terms of ∣Φ∣|\Phi|, but that is an intermediate representation to the algorithm. The complexity should be stated in terms of the input/parameters (n,ℓ,m,k,D,εn, \ell, m, k, D, \varepsilon). For example, in the doubling dimension regime, writing ∣Φ∣|\Phi| can hide the (32/ε)D(32/\varepsilon)^D term and makes the communication/complexity/approximation tradeoff unclear.

3 comments
AuthorsOpenReview ↗

Response to Reviewer E8Se

Thank you for your careful review and for recognizing the theoretical value of our paper, particularly the improvement in the approximation factor from 1717 to 77. We regard the 1717-approximation of Chiplunkar et al. (ICML 2020) as an elegant and technically substantial result. Their work laid an important foundation for distributed fair kk-center clustering and established a strong benchmark that is challenging to improve upon. Below are our responses to the concerns and questions you raised.

[Weakness 1] Tradeoffs among the three metric regimes and guidance on when to use each variant.

[Response] Thank you for this suggestion. The choice among our algorithms depends on the tradeoff between a stronger approximation guarantee and the additional computation and communication it requires. In particular, the doubling-metric variant has a (32/ε)D(32/\varepsilon)^D dependence in its summary-size bound, whereas the Euclidean variant retains at most 122km122km point records per worker.

Thus, for the reviewer's example of high-dimensional Euclidean data with low intrinsic doubling dimension, we would choose the doubling-metric algorithm if its additional computation, communication, and memory costs are affordable, and the Euclidean algorithm otherwise. We will add this guidance to the revised manuscript.

[Weakness 2] Scope of the communication lower bound and its relationship to existing lower bounds.

[Response] Thank you for examining our communication lower bound and confirming its correctness. You are right that the lower bound uses ℓ=Θ(n)\ell=\Theta(n) workers. We will compare this result with the lower bound established using an elegant construction by Chiplunkar et al. (ICML 2020): a factor-44 obstruction for unconstrained kk-center with a constant number of workers. In contrast, our result considers fair center selection under the stated information restrictions and a different worker regime. We will clarify these assumptions and the relationship to prior work in the revised manuscript.

[Q1] Whether the Euclidean result is the first dimension-independent constant-factor guarantee or an improvement over an existing guarantee.

[Response] The 5.845.84 guarantee is a dimension-independent improvement, rather than the first dimension-independent constant-factor guarantee in this model: the earlier 1717-approximation for general metrics also applies to Euclidean inputs.

[Q2] How the coordinator work of the doubling-metric and Euclidean algorithms compares with prior work.

[Response] The three variants use the same coordinator structure. For one radius test, the coordinator requires O(k∣Φ∣)O(k|\Phi|) distance evaluations and a maximum-flow computation on a graph with O(k+m)O(k+m) vertices and O(km)O(km) edges. With a direct augmenting-path implementation and constant-time distance evaluations, the total coordinator time is O(k∣Φ∣+k2m)O(k|\Phi|+k^2m), and its space usage is O(∣Φ∣+km)O(|\Phi|+km).

For our general-metric variant, substituting ∣Φ∣≤ℓmk|\Phi|\leq \ell mk gives the same worst-case asymptotic coordinator time, O(ℓmk2)O(\ell mk^2), as Chiplunkar et al. (ICML 2020), with a better approximation factor. The doubling-metric and Euclidean variants use larger summaries, which increase the coordinator's scanning time and storage, while the flow-network size remains unchanged. Wu et al. (AAMAS 2024) likewise combine geometric summary processing with matching-based quota enforcement.

[Q3] What running time includes in the experimental results.

[Response] Thank you for this question. The reported running time includes computation on both the workers and the coordinator under simulated parallel execution.

[Q4] Expressing the complexity bounds in terms of input parameters rather than the intermediate summary size ∣Φ∣|\Phi|.

[Response] Thank you for this suggestion. We originally used ∣Φ∣|\Phi| to state the coordinator complexity bounds concisely across the three metric settings. We agree that this may obscure their dependence on DD and ε\varepsilon. The total communication (in point records) and coordinator time for one radius test are bounded as follows, with communication listed first and coordinator time second:

  • General metrics: min⁡n,ℓmk\min\\{n,\ell mk\\}; O(kmin⁡n,ℓmk+k2m)O(k\min\\{n,\ell mk\\}+k^2m).
  • Doubling metrics: min⁡n,ℓmk(32/ε)D\min\\{n,\ell mk(32/\varepsilon)^D\\}; O(kmin⁡n,ℓmk(32/ε)D+km+MF⁡(k+m,km))O(k\min\\{n,\ell mk(32/\varepsilon)^D\\}+km+\operatorname{MF}(k+m,km)).
  • Euclidean spaces: min⁡n,122ℓmk\min\\{n,122\ell mk\\}; O(Dkmin⁡n,122ℓmk+k2m)O(Dk\min\\{n,122\ell mk\\}+k^2m).

The first two time bounds assume constant-time distance evaluations; the Euclidean bound counts arithmetic operations on explicitly represented DD-dimensional points. We will state these bounds directly in the revised paper.

Thanks again for your in-depth comments and valuable advices. We are happy to answer any follow-up questions.

Dear Reviewer E8Se,

Thank you for your in-depth comments and the valuable advices. As the discussion period approches its end, we would appreciate it if you could let us know whether it addresses your concerns. We are happy to answer any follow-up questions.

Best Regards,

Reviewer_cb3mOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies approximation algorithms for fair k-center clustering in the MPC model of computation. Here, the points are distributed distributed into m groups, and additionally they are distributed across machines. The goal is to ensure a small amount of total communication, while still achieving a constant factor approximation to the fair k-center objective (at most a certain number of centers chosen from each group).

The authors study a natural two-stage process (the merge-reduce paradigm), where the machines run the classic Gonzales algorithm, effectively reducing the number of points per group per machine to roughly k. These are accumulated at a central server, which effectively solves the overall problem. The final approximation factor is 7+\epsilon for general metrics. For metrics with small doubling dimension, the same framework gives a (3+\epsilon) approximation, but the number of points used grows exponentially in the dimension parameter. The approximation factor is also improved for Euclidean metrics (obtaining a factor roughly 5.8).

Critical strengths

The paper obtains better approximation factors for the considered objective. This is somewhat interesting, but to a very niche audience on fairness and approximation algorithms.

Critical weaknesses

The novelty is very limited. The "MPC" aspect of the problem is very minimal; machines do the most natural procedure of running Gonzales on each group and send it all to a central server. Much of the work is done by the central server, which runs a flow based procedure. The improvements in the approximation factor seem to come from a slightly improved analysis (over the work of Chiplunkar et al. 2020), along with analysis of the single machine algorithm. Overall the result is not strong enough for a venue like ICLR.

Questions for authors

If there are parts of the paper that are particularly novel (either algorithmically or in the analysis, modulo slight constant improvements), the authors should highlight it.

3 comments
AuthorsOpenReview ↗

Response to Reviewer cb3m

Thank you for your careful reading and assessment of our work. Below is our response to your concern.

[Weakness & Question] Novelty and contribution of our work.

[Response] Thank you for the comment.

First, under the same radius-given assumption, our algorithm improves the approximation factor from 1717 to 77 while retaining one communication round and O(km)O(km) transmitted point records per worker. We believe this improvement in the approximation ratio is significant.

Second, the key difference between our algorithm and that of Chiplunkar et al. lies in the local computation. Their key idea is to first select local pivots without considering group labels. They then retain and transmit nearby representatives from the relevant groups to support the same-group replacement argument in their proof. In contrast, our algorithm runs Gonzalez traversal separately within each group from the beginning of local computation.

Although this algorithmic modification is modest, to the best of our knowledge, ours is the first work to exploit this component to improve the approximation ratio under the same communication bound. The proof framework of Chiplunkar et al. does not directly yield this improved guarantee. We therefore provide a new proof framework, starting with Lemmas 1 and 2, which are key to our subsequent analysis. Thus, our improved approximation factor comes from a different algorithmic construction and its analysis.

Third, at the coordinator, we construct a separated representative set and use a quota-constrained flow whose feasibility is established in Lemma 4. We acknowledge that this is a standard method for handling quota constraints, similar to the matching-based and hitting-set-based tools used in previous work. Our group-wise summaries enable the sharper coverage and feasibility guarantees used in our analysis.

Thanks again for your valuable comments. We are happy to answer any follow-up questions.

Dear Reviewer cb3m,

Thank you for your valuable comments as well the question and the advice. As the discussion period is approching its end in roughly three days, we would appreciate it if you could review our rebuttal and kindly let us know whether it addresses your concerns.

Best Regards,

Reviewer_cb3mOpenReview ↗

comment on rebuttal

I appreciate the author's rebuttal and comments. As the review says, yes there is certainly an improvement in the approximation factor and there is certainly a change in the algorithm, but I still don't see the paper as strong enough in terms of novelty.. (It is still a combination of simple methods, I don't see a proof "framework" here).

I would maintain my score, and acknowledge the rebuttal.

Reviewer_9rG2OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The paper gives a one-round coordinator algorithm for fair k-center with group upper bounds: each worker runs farthest-first traversal separately on every group, and the coordinator picks centers using a separated set and a capacitated max flow. This gives a 7+ \epsilon approximation with O(kml) communication, improving the previous factor of 17. Its other results are 3+\epsilon in doubling metrics and about 5.84 in Euclidean space, plus an Omega(n) communication lower bound for factors below 5. The approach is tested empirically on real world datasets.

Critical strengths
  1. The paper proposes a simple method which is easy to verify
  2. There is no dependence on r*
  3. Empirical evaluation shows interesting results
Critical weaknesses
  1. Overlap with prior work, and how that work is described. The method may not be new compared with Bera et al. (WWW 2022), and Chiplunkar et al. (2020), which use the same approach: local summaries, then group-capacitated selection at the coordinator. Bera et al. is described as a different fairness notion and not compared against. The authors should say what is new beyond one round and per-group Gonzalez.

  2. Experiments: Communication is never measured. The main contribution is a trade-off between approximation and communication, yet no experiment reports how many points each method sends. This matters most for the doubling variant and the Euclidean variant.

  3. Cost is measured in l1 but centers are chosen in l2?

  4. 100x runtime gap with Chiplunkar (D) is potentially because of implementation difference and not algorithmic difference alone. Please quantify the correct difference.

  5. The paper is better suited for a TCS or a data mining conference.

Questions for authors

Please clarify overlap with prior work and the issues with experiments.

5 comments
AuthorsOpenReview ↗

Responses to Reviewer 9rG2

Thank you for the review. Below are our point-by-point responses to the weaknesses you raised.

[Weakness 1 &Question 1] Concerns about overlap with Bera et al. (WWW 2022) and Chiplunkar et al. (ICML 2020), and about the novelty of our contribution.

[Response] Thank you for raising this question. First, Bera et al. (WWW 2022) study a different fairness constraint, which bounds the proportion of points from each protected group within each cluster. Their coordinator uses an LP for fair point-to-center assignment, whereas our problem constrains the group composition of the selected centers. Their approximation algorithm, as well as the analysis, therefore addresses a different constrained problem.

Our algorithm and analysis also differ from those of Chiplunkar et al. (ICML 2020), who study the same data-summarization fairness notion. The key algorithmic difference lies in local summary construction: Chiplunkar et al. (ICML 2020) and Wu et al. (AAMAS 2024) first select local geometric candidates without using group labels. Their analyses use the covering properties of these candidates and then rely on group-specific representatives to obtain nearby same-group replacements for optimal centers.

In contrast, we run Gonzalez traversal separately within each local group. This construction yields the coverage properties in Lemmas 1 and 2. Together with the flow feasibility established in Lemma 4, these properties allow us to achieve a better approximation ratio while retaining O(km)O(km) transmitted point records per worker.

Therefore, the novelty lies in our local summary construction and its associated analysis. Our results show that incorporating group labels into local geometric selection can improve the approximation ratio for fair kk-center in the MPC model.

[Weakness 2] The absence of empirical communication measurements, particularly for the doubling-metric and Euclidean variants.

[Response] The main contribution of our paper is a stronger approximation guarantee under a fixed communication-round constraint. In MPC, the number of communication rounds is a primary measure, just as the number of passes is in streaming algorithms. We also provide theoretical bounds on the number of transmitted point records, including the (32/ε)D(32/\varepsilon)^D and 122122 factors for the doubling-metric and Euclidean variants, respectively.

Chiplunkar et al. (ICML 2020) and Wu et al. (AAMAS 2024) likewise provide theoretical communication bounds while focusing their experiments on clustering cost and running time. We follow this evaluation approach.

[Weakness 3] The use of ℓ2\ell_2 distance for center selection and ℓ1\ell_1 distance for cost evaluation.

[Response] On the real-world datasets, only the algorithm for Euclidean space (i.e., Ours) uses ℓ2\ell_2 distance for center selection, as explicitly stated in our experimental setup. These datasets are also used by several baselines, including Chiplunkar et al. (ICML 2020), and we follow their ℓ1\ell_1-based setting when evaluating clustering cost. To include Ours (Euclidean) in the same comparison, we evaluate its returned centers using the same ℓ1\ell_1 cost as the other methods.

The 5.845.84 guarantee applies to the Euclidean objective and is not claimed for these ℓ1\ell_1 evaluations. On SynA, both center selection and cost evaluation use ℓ2\ell_2 distance. We will clarify this distinction in the revised manuscript.

[Weakness 4] The approximately 100-fold runtime gap observed on some datasets.

[Response] All methods were evaluated in the same experimental environment. For Chiplunkar et al. (D), we used an implementation based on the source code released by the authors. The approximately 100-fold gap refers to the running times observed on Adult under specific settings. All code and datasets are available in the supplementary materials.

[Weakness 5] The paper's fit with ICLR relative to TCS or data mining conferences.

[Response] Our paper studies fair data summarization for large-scale machine learning, combining distributed algorithms, approximation guarantees, and empirical evaluation. These contributions connect to large-scale learning, learning theory, and fairness. Moreover, closely related work, including Kleindessner et al. (ICML 2019), Chiplunkar et al. (ICML 2020) and Jones et al. (ICML 2020), has appeared at leading machine learning conferences. We therefore believe the paper is relevant to ICLR, and we appreciate the reviewer's perspective.

Thanks heaps for your valuable comments. We are happy to answer any follow-up questions.

Dear Reviewer 9rG2,

Thank you for your valuable comments. As the discussion period ends in three days, we would appreciate it if you could review our rebuttal and let us know whether it addresses your concerns.

Best Regards,

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Our Responses to the Reviewers

Dear Area Chair,

Thank you for overseeing the review process. First, we thank the reviewers for unanimously agreeing that our algorithms are sound and reliable. In particular, we thank Reviewer E8Se for their careful reading, detailed technical questions, and recognition of our contribution.

We would like to briefly summarize our clarifications provided in our rebuttal as follows.

(1)Novelty relative to previous work (Reviewers 9rG2 and cb3m).

Our main result improves the approximation factor for distributed fair kk-center from 1717 to 77, under the same radius-given assumption, while retaining one communication round and O(km)O(km) transmitted point records per worker. This improves upon the elegant result of Chiplunkar et al. (ICML 2020), which established a strong benchmark for subsequent research.

We emphasize that our algorithm and analysis differ from those of Chiplunkar et al. We run Gonzalez traversal separately within each local group. Lemma 1 establishes that our summaries contain a quota-feasible solution covering the original input within 3τ3\tau, enabling the improved approximation analysis. The earlier 5τ5\tau guarantee concerns coverage of the local pivots.

We therefore believe that these algorithmic and analytical differences provide sufficient novelty.

(2) The concern that the “MPC” aspect of the problem is minimal (Reviewer cb3m).

The MPC model is widely used as a theoretical framework for large-scale parallel processing systems, including MapReduce. Related research on approximation algorithms and optimization in this model has appeared at major venues, including ICML, NeurIPS, STOC, FOCS, and SODA. Within this model, our contribution is to show how independently constructed group-wise summaries support an improved global approximation while retaining one worker-to-coordinator communication round and the same asymptotic per-worker communication bound.

(3) Empirical communication measurements (Reviewer 9rG2).

In the MPC model, the number of communication rounds is a primary measure, just as the number of passes is in streaming algorithms. Chiplunkar et al. (ICML 2020) and Wu et al. (AAMAS 2024) likewise provide theoretical communication bounds while focusing their experiments on clustering cost and running time. We follow this evaluation approach.

(4) The approximately 100-fold runtime gap observed on some datasets (Reviewer 9rG2).

For Chiplunkar et al. (D), we used an implementation based on the source code released by Chiplunkar et al. (ICML 2020). All our code and datasets are available in the supplementary material.

We have also addressed the reviewers’ other concerns and would be happy to answer any follow-up questions. In addition, for ease of reference, we have included the appendix in the revised manuscript (The appendix was already provided in our previous supplementary material).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.