- 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 , partitioned in two ways: disjoint groups () and workers (), each group has a specified number of centers 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 . Results include 3 regimes:
- A 7-approximation in general metrics; points communication; work per partition; coordinator work, where 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 , and , a -approximation and points communication. This inproves the approximation from in prior work while increasing communication by a factor of .
- In Euclidean spaces a 5.84-approximation using points communication.
The authors also give a 5-approximation lower bound for workers (any lower factor requires 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 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 , but that is an intermediate representation to the algorithm. The complexity should be stated in terms of the input/parameters (). For example, in the doubling dimension regime, writing can hide the term and makes the communication/complexity/approximation tradeoff unclear.
3 comments
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,
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 17 to 7. We regard the 17-approximation of Chiplunkar et al. (ICML 2020) as an elegant and technically substantial result. Their work laid an important foundation for distributed fair k-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 dependence in its summary-size bound, whereas the Euclidean variant retains at most 122km 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) workers. We will compare this result with the lower bound established using an elegant construction by Chiplunkar et al. (ICML 2020): a factor-4 obstruction for unconstrained k-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.84 guarantee is a dimension-independent improvement, rather than the first dimension-independent constant-factor guarantee in this model: the earlier 17-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∣Φ∣) distance evaluations and a maximum-flow computation on a graph with O(k+m) vertices and O(km) edges. With a direct augmenting-path implementation and constant-time distance evaluations, the total coordinator time is O(k∣Φ∣+k2m), and its space usage is O(∣Φ∣+km).
For our general-metric variant, substituting ∣Φ∣≤ℓmk gives the same worst-case asymptotic coordinator time, O(ℓmk2), 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 ∣Φ∣.
[Response] Thank you for this suggestion. We originally used ∣Φ∣ to state the coordinator complexity bounds concisely across the three metric settings. We agree that this may obscure their dependence on D and ε. 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:
The first two time bounds assume constant-time distance evaluations; the Euclidean bound counts arithmetic operations on explicitly represented D-dimensional points. We will state these bounds directly in the revised paper.