- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies the k-center clustering with outliers and its fair variant, in MapReduce setting. The key idea is to keep a summary of z+1 nearby witnesses for each discarded point. The authors provide a 6-approximation for k-center with outliers and an 11-approximation for the fair variant ((6+epsilon) and (11+epsilon) when the optimal radius is guessed).
Critical strengths
- The paper studies a classic ML problem, namely k-center with outliers and its fair version in a distributed (MapReduce) setting.
- The methods appear to be technically correct.
Critical weaknesses
- The MapReduce model is somewhat dated, although the authors also state their results as an MPC model, so it might be a matter of presentation.
- The technical proofs are not particularly deep and the ideas mostly standard.
- The per worker computation is multiplicative in k and z, which might be large for certain application. Also curious if there is a lower bound.
- The authors are pointing to an Appendix, but as far as I can tell, there is no appendix. Also, the experimental results include only the standard version (no fair variant). Those could be in the missing appendix.
- The overall fit to ICLR might be a bit weak and the paper might fit better a theory or KDD-type conference.
Questions for authors
- Please respond about the lower bound and missing appendix.
5 comments
Dear Reviewer W4Pm,
Thank you for your time and effort in reviewing our paper. We appreciate your valuable comments, which have helped us improve its quality. As the author–reviewer discussion period will end in approximately three days, we would be grateful if you could review our rebuttal and let us know whether it addresses your concerns. Thank you again for your time and consideration.
Best regards,
The Authors of Submission 5793
Dear Reviewer W4Pm,
Thank you again for your time and effort in reviewing our manuscript. As the author–reviewer discussion period ends in about 30 hours, we would sincerely appreciate any feedback you may be able to share on our response. We would be happy to address any questions or concerns. Thanks a lot.
Best regards,
The Authors of Submission 5793
Response to Reviewer W4Pm
Thank you for your careful review and constructive feedback. We appreciate your positive assessment of the paper's clarity and the soundness of our methods. Then, we provide our response below.
Response. Thank you for this comment. As discussed in [1], the massively parallel computation (MPC) model provides a theoretical abstraction of MapReduce and related large-scale distributed frameworks. MPC continues to attract research attention, including recent work on fully scalable Euclidean k-center clustering at ICALP 2025 [2] and directed densest-subgraph algorithms at NeurIPS 2025 [3].
[1] Orr Fischer, Adi Horowitz, and Rotem Oshman. Massively parallel computation in a heterogeneous regime. Distributed Computing, 38:185–206, 2025.
[2] Artur Czumaj, Guichen Gao, Mohsen Ghaffari, and Shaofeng H.-C. Jiang. “Fully Scalable MPC Algorithms for Euclidean k-Center.” ICALP 2025, LIPIcs 334, pp. 64:1–64:20.
[3] Slobodan Mitrovic, Theodore Pan, Mahdi Qaempanah, and Mohammad Amin Raeisi. “New Parallel and Streaming Algorithms for Directed Densest Subgraph.” Advances in Neural Information Processing Systems 38, 2025
Response. Thank you for this comment. Our algorithms offer an alternative approximation–space trade-off, achieving (6+ε)- and (11+ε)-approximations for distributed k-center with outliers and its fair variant, respectively, which are the best approximation ratios in general metric spaces, with polynomial running time and local summary-size bounds. As Table 1 shows, our first algorithm improves upon the published 13-approximation of OUTLIERS-MR, while both algorithms avoid the exponential dependence on doubling dimension in the summary-size bounds of the compared coreset methods.
In addition, the unweighted summaries preserve z+1 distinct nearby witnesses, allowing coverage to transfer to the original input without increasing the outlier budget. For the fair variant, same-group candidates, LP-guided filtering, and matching weighted by block sizes jointly enforce group upper bounds while covering at least ∣S∣−z summary points.
Response. Thank you for this comment. We need to clarify that the per worker computation (e.g. time complexity) is O(niqi[k(z+1)+z]) time for the distributed k-center with outliers problem and O(niqi[k(z+g+1)+z]) for the fair variant, where ni=∣Pi∣ and qi≤1+⌈log(1+ε)logΔi⌉,Δi=minu,v∈Pid(u,v)maxu,v∈Pid(u,v) for u=v.
Previous methods offer different trade-offs. For example, Huang et al. (2023) provide a local running-time bound without multiplicative dependence on z, while allowing up to (1+ε)z outliers. Our additional dependence supports the unweighted witness summaries that preserve the outlier budget.
We do not establish a lower bound on per-worker computation and do not claim that the multiplicative dependence on k and z is necessary.
Response. Thank you for the comment; we have supplied the appendix and main body in the original submission. Now, we have updated the full version in the revision submitted.
Response. Thank you for this perspective. Our work addresses robust and fair representative selection from distributed data. We believe it has a tight connection with ICLR because several closely related studies have appeared at leading machine learning conferences, including Malkomes et al. (NeurIPS 2015), Huang et al. (ICML 2023), and Chiplunkar et al. (ICML 2020).