acceptodds
Under review as a conference paper at ICLR 2027

Improved Approximations for Distributed -Center Clustering with Outliers and Fairness

Abstract

Selecting representatives from distributed data requires geometric coverage, robustness to outliers, and control over group representation among the selected centers. We study -center clustering with outliers and its fair extension, which imposes bounds on the number of centers selected from each of disjoint groups. We develop a two-round MapReduce framework for both problems in general metric spaces. The framework uses an unweighted summary that preserves nearby witnesses for every omitted point. Consequently, covering all but at most summary points allows coverage to be extended to the original dataset without increasing the outlier budget. For -center with outliers, a greedy merging procedure achieves a -approximation using point records per worker. For the fair extension, we additionally preserve nearby same-group candidates and combine LP-guided filtering with maximum-weight bipartite -matching to obtain a first -approximation using point records per worker. These factors hold when the optimal radius is supplied. By guessing the radius, our method yields - and -approximations, respectively, with the number of guesses charged explicitly in communication. Finally, we complement our theoretical results with experiments on six real-world datasets and a synthetic dataset with known optimal solutions, demonstrating substantial improvements in clustering utility over state-of-the-art methods.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
clustering, outlier, massive parallel computation, fairness

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_W4PmOpenReview ↗
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
AuthorsOpenReview ↗

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.

W1. 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.

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 kk-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

W2. The technical proofs are not particularly deep and the ideas mostly standard.

Response. Thank you for this comment. Our algorithms offer an alternative approximation–space trade-off, achieving (6+ε)(6+\varepsilon)- and (11+ε)(11+\varepsilon)-approximations for distributed kk-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 1313-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+1z+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|S|-z summary points.

W3. 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.

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])O(n_iq_i[k(z+1)+z]) time for the distributed kk-center with outliers problem and O(niqi[k(z+g+1)+z])O(n_iq_i[k(z+g+1)+z]) for the fair variant, where ni=∣Pi∣n_i=|P_i| and qi≤1+⌈log⁡Δilog⁡(1+ε)⌉,Δi=max⁡u,v∈Pid(u,v)min⁡u,v∈Pid(u,v)q_i\le 1+\left\lceil \frac{\log\Delta_i}{\log(1+\varepsilon)} \right\rceil, \Delta_i= \frac{\max_{{u,v\in P_i}}d(u,v)}{\min_{{u,v\in P_i}}d(u,v)} for u≠vu\ne v.

Previous methods offer different trade-offs. For example, Huang et al. (2023) provide a local running-time bound without multiplicative dependence on zz, while allowing up to (1+ε)z(1+\varepsilon)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 kk and zz is necessary.

W4. 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.

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.

W5. The overall fit to ICLR might be a bit weak and the paper might fit better a theory or KDD-type conference.

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).

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

Reviewer_er3iOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper addresses the problem of kk-center clustering with outliers in general finite metric space (P,d)(P,d) where the goal is to report a set CC of kk points from PP that minimize the maximum distance when ignoring a budget of (the worst) zz outliers from PP. They further extend this classical problem to the case where the clustering has to be "fair", that is the input dataset PP is further partitioned to gg groups and gg integers are given, k1,...,kgk_1,...,k_g, and the clustering must obey the restriction that the ii'th group include at most kik_i representatives in CC.

The paper consider the distributed settings (MapReduce framework), where the data is partitioned across mm machines (workers). In their results there are two rounds of computation: Each machine construct a summary and send it to a designated coordinator which aggregates the summaries to a final solution.

The paper main contribution is via theoretical analyses and proofs.

The main theorems:

  1. For k-center with zz outliers the paper shows a two rounds algorithm that provide 6-approximation with mk(z+1)+z communication (points).
  2. For fair k-center with zz outliers the paper shows a two rounds algorithm that provide 11-approximation with mk(z+g+1)+z communication (points).

The main technical insight is that for every point in P there are at least z+1z+1 neighbors in the summary, which allows the summaries to be effective when aggregated to the k-centers.

The results assume knowledge of the optimal cost, and otherwise, with simple binary search on the aspect ratio an approximate (6+ϵ),(11+ϵ)(6+\epsilon),(11+\epsilon) results can be obtained.

The first result improve over previous 13-approximation result (Malkomes et al., Neurips 2015), but with much higher communication, so the results are not directly comparable. The second result, for fair clustering, is the first in the distributed model.

Critical strengths
  1. The problems of k-centers and fair k-centers are standard and extensively studied.
  2. The algorithm is elegant and easy to implement, the proofs are well-written and sound. Yet, I think the writing can be further improved by introducing less notations.
Critical weaknesses
  1. the contribution is minor as there is no clear improvement over previous work: a. In order to overcome the fact that the optimal solution RR is unknown the algorithm have to rerun ϵ−1log⁡Rmax/Rmin\epsilon^{-1} \log R_{max} / R_{min} times, which break the 2-rounds results. This is not the case in previous works. b. The summary total size is large O(kmz)O(kmz) as oppose to O(km)O(km) in previous results.
  2. The local running time is not analyzed.
  3. Several citations and proper comparison with previous work is missing: Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, and David P. Woodruff. Robust Communication-Optimal Distributed Clustering Algorithms. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.18

Guha, Sudipto, Yi Li, and Qin Zhang. "Distributed partial clustering." ACM Transactions on Parallel Computing (TOPC) 6.3 (2019): 1-20.‏

Li, Shi, and Xiangyu Guo. "Distributed $ k $-Clustering for Data with Heavy Noise." Advances in Neural Information Processing Systems 31 (2018).‏

  1. there is no clear/significant improvement in practice.
Questions for authors
  1. Can the authors compare with previous work and highlight the main advantages/disadvantages of this work, perhaps using a table?
  2. Can the authors compare their work in terms of running time?
  3. The abstract contain big O notations, I think those should be removed or at least make use of the O notation to simplify the terms.
  4. Many notations are introduced but not really needed, the text can benefit from less notations, like τ,r∗,U\tau, r^*,U. See also small typo in line 159.
  5. The main theorems are written in a different fashion, I don't see a reason for that.
8 comments
AuthorsOpenReview ↗

Response to Reviewer er3i

Thank you for recognizing the soundness of our results and for your detailed comments and questions. Our work offers a trade-off among approximation quality, summary size, and computation. We obtain (6+ε)(6+\varepsilon)- and (11+ε)(11+\varepsilon)-approximations for the ordinary and fair problems, respectively.

W1. the contribution is minor as there is no clear improvement over previous work: a. In order to overcome the fact that the optimal solution RR is unknown, the algorithm has to rerun ε−1log⁡(Rmax⁡/Rmin⁡)\varepsilon^{-1}\log(R_{\max}/R_{\min}) times, which breaks the two-round result. This is not the case in previous work. b. The summary total size is large O(kmz)O(kmz) as oppose to O(km)O(km) in previous results.

Response. Thank you for this valuable comment.

  • In the revised manuscript, we handle the unknown optimal radius through adaptive local summarization and an independent coordinator search. The algorithm admits a two-round MapReduce implementation, with only one round of summary communication after the initial input distribution.

    • In the first round, reducers construct local summaries in parallel, performing all local radius trials internally. In the second round, the final summaries are gathered at a designated reducer, which performs all coordinator threshold trials and computes the final solution locally. Thus, repeated radius trials do not increase the number of MapReduce rounds or introduce a multiplicative radius-guessing factor in communication.
  • Regarding summary size, we acknowledge the additional dependence on zz. This supports the preservation of z+1z+1 distinct nearby witnesses for every omitted point, allowing coverage to transfer to the original dataset without increasing the outlier budget. Our contribution is therefore an approximation–space trade-off: (6+ε)(6+\varepsilon)-approximations with O(kmz)O(kmz) summary total size, compared with the previous work's (13+ε)(13+\varepsilon)-approximations with O(m(k+z))O(m(k+z)) summary total size. We have clarified this trade-off in Table 1 and the revised discussion.

W2. The local running time is not analyzed.

Response. We add two lemmas (i.e., Lemmas 13 and 14) to state the running time as below (also added in the revised manuscript).

Lemma 13. Let ni=∣Pi∣n_i=|P_i|, let qiq_i denote the number of local construction trials performed by worker ii, and assume 0<ε<10<\varepsilon<1. In Algorithm 1, the total time spent on local construction trials is O(niqi[k(z+1)+z])O\left(n_iq_i[k(z+1)+z]\right), where qi≤1+⌈log⁡Δilog⁡(1+ε)⌉,Δi=max⁡u,v∈Pid(u,v)min⁡u,v∈Pid(u,v)q_i\le 1+\left\lceil \frac{\log\Delta_i}{\log(1+\varepsilon)}\right\rceil,\Delta_i= \frac{\max_{{u,v\in P_i}}d(u,v)}{\min_{{u,v\in P_i}}d(u,v)} for u≠vu\ne v.

Proof. With immediate termination upon exceeding the size cap, each processed point is compared with at most k(z+1)+zk(z+1)+z retained points. A trial processes at most nin_i points and therefore takes O(ni[k(z+1)+z])O(n_i[k(z+1)+z]) time. The radius is increased geometrically from Rmin⁡R_{\min} by a factor of 1+ε1+\varepsilon until a successful trial is found. Summing the costs over the qiq_i trials gives O(niqi[k(z+1)+z]).O\left(n_iq_i[k(z+1)+z]\right).

Lemma 14. Let ni=∣Pi∣n_i=|P_i|, let qiq_i denote the number of local construction trials performed by worker ii, and assume 0<ε<10<\varepsilon<1. In Algorithm 2, the total time spent on local construction trials is O(niqi[k(z+g+1)+z]),O\left(n_iq_i[k(z+g+1)+z]\right), where qi≤1+⌈log⁡Δilog⁡(1+ε)⌉,Δi=max⁡u,v∈Pid(u,v)min⁡u,v∈Pid(u,v)q_i\le 1+\left\lceil \frac{\log\Delta_i}{\log(1+\varepsilon)} \right\rceil, \Delta_i= \frac{\max_{{u,v\in P_i}}d(u,v)}{\min_{{u,v\in P_i}}d(u,v)} for u≠vu\ne v.

Proof. During each trial, processing a point requires checking its nearby witnesses in SiS_i and same-group candidates in TiT_i. With immediate termination upon exceeding the cap k(z+g+1)+zk(z+g+1)+z, these checks take O(k(z+g+1)+z)O(k(z+g+1)+z) time per point. Thus, each trial takes O(ni[k(z+g+1)+z])O(n_i[k(z+g+1)+z]) time. The radius is increased geometrically from Rmin⁡R_{\min} by a factor of 1+ε1+\varepsilon until a successful trial is found. Summing the costs over the qiq_i trials gives O(niqi[k(z+g+1)+z]).O\left(n_iq_i[k(z+g+1)+z]\right).

W3. Several citations and proper comparison with previous work are missing:

  • Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, and David P. Woodruff. Robust Communication-Optimal Distributed Clustering Algorithms. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.18
  • Guha, Sudipto, Yi Li, and Qin Zhang. "Distributed partial clustering." ACM Transactions on Parallel Computing (TOPC) 6.3 (2019): 1-20.
  • Li, Shi, and Xiangyu Guo. "Distributed k-Clustering for Data with Heavy Noise." Advances in Neural Information Processing Systems 31 (2018).

Response. Thank you for pointing out these relevant references. We have added them and expanded the related-work discussion to compare their results in the resubmission version in Subsection 1.1.

AuthorsOpenReview ↗

Response to Reviewer er3i - continue

W4. there is no clear/significant improvement in practice.

Response. Thank you for this comment. We briefly summarize our experimental results below to highlight the clear practical improvement of our work.

Across four real-world datasets, our evaluated implementation, including post-processing, achieves lower mean objective values than the best-performing baseline in each configuration among CPP19-Det, CPP19-Rand, and Outliers-MR. The reductions range from 4.32% to 17.05%, averaging 9.80% across the plotted comparisons. We have updated Section 5.1 to quantify these improvements more explicitly.

Synthetic experiments with empirical approximation ratio (Figure 3), with both algorithms achieving factors well below their theoretical worst-case bounds.

  • For D$k$CO, our algorithm is competitive with the CPP19 variants and achieves consistently lower empirical approximation factors than Outliers-MR. The CPP19 variants offer stronger theoretical approximation guarantees, with summary-size bounds that depend exponentially on the doubling dimension DD.
  • For DF$k$CO, our fair algorithm is competitive with MRCoreset and substantially outperforms Yuan-Dist in the synthetic experiments.

Q1. Can the authors compare with previous work and highlight the main advantages/disadvantages of this work, perhaps using a table?

Response. Thank you for this suggestion. The following tables summarize the comparison with previous results.

ProblemPaper / methodApproximationAllowed outliersTotal communication
Distributed kk-center with outlierMalkomes et al. (2015)13+ε13+\varepsilonzzO(m(k+z))O(m(k+z))
Distributed kk-center with outlierLi and Guo (2018)24(1+ε)24(1+\varepsilon)(1+ε)z(1+\varepsilon)zO(mklog⁡Δ/ε2)O(mk\log\Delta/\varepsilon^2)
Distributed kk-center with outlierGuha et al. (2019)O(1)O(1)zzO~(mk+z)\widetilde{O}(mk+z)
Distributed kk-center with outlierCeccarello et al. (2019)⋆^\star3+ε3+\varepsilonzzO(m(k+z)(24/ε)D)O(m(k+z)(24/\varepsilon)^D)
Distributed kk-center with outlierHuang et al. (2023)†^\dagger14(1+ε)14(1+\varepsilon)(1+ε)z(1+\varepsilon)zO(mklog⁡mlog⁡Δ/ε2)O(mk\log m\log\Delta/\varepsilon^2)
Distributed kk-center with outlierOurs6+ε6+\varepsilonzzO(mkz)O(mkz)
Distributed fair kk-center with outlierCeccarello et al. (2023)⋆^\star3+ε3+\varepsilonzzO(mk(k+z)(c/ε)D)O(mk(k+z)(c/\varepsilon)^D)
Distributed fair kk-center with outlierOurs11+ε11+\varepsilonzzO(mk(z+g))O(mk(z+g))

⋆^\star The communication bound depends exponentially on the doubling dimension DD.

†^\dagger The approximation guarantee holds with constant probability.

The summary-size bounds of Ceccarello et al. (2019) and (2023) depend exponentially on the doubling dimension DD, and can not work for general metrics. Our algorithms offer an alternative approximation–space trade-off, achieving (6+ε)(6+\varepsilon)- and (11+ε)(11+\varepsilon)-approximations for distributed kk-center with outliers and its fair variant, respectively, which are best approximation ratios in general metric spaces, with polynomial running time and local summary-size bounds.

Q2. Can the authors compare their work in terms of running time?

Response. Thank you for the question. We have provided the runtime comparison with related works in Appendix C.2.3.

Q3-5. The abstract contains big-OO notation, which should be removed or simplified. Many notations are introduced but are not really needed; the text could benefit from fewer notations, such as τ\tau, r∗r^*, and UU. There is also a small typo in line 159. The main theorems are written in different formats.

Response. Thank you for these suggestions. We have double-checked the presentation and revised them in the revision and highlighted them in color.

I thank the authors for their detailed response and the substantial effort they put into the revision. However, the revision adds a significant amount of new content, which would require a careful, fresh round of review beyond the scope of the rebuttal phase. Additionally, the revision does not resolve my second main concern, namely the dependence on zz. I therefore maintain my score.

Reviewer_yBzEOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes a two-round MapReduce framework to address both the distributed k-center clustering with outliers (DkCO) problem and its fair extension (DFkCO) in general metric spaces. The core mechanism introduces an unweighted summarization strategy that retains z+1z+1 nearby witnesses for every omitted point, ensuring that any points removed as outliers will not completely eliminate the representatives of locally covered data.
For the unconstrained kCO problem, the authors introduce a greedy merging procedure that yields a 6-approximation when the optimal radius is known, or a (6+ϵ)(6+\epsilon)-approximation when employing a radius-guessing strategy. For the fair extension, the framework preserves same-group candidates and applies an LP-guided filtering step coupled with maximum-weight bipartite b-matching. This achieves an 11-approximation (or 11+ϵ11+\epsilon) while satisfying group representation upper bounds and the overall outlier budget. The framework theoretically improves upon previous works by bounding local summary sizes independently of the doubling dimension. The authors evaluate their methods on synthetic and six real-world datasets, demonstrating competitive or superior clustering costs compared to state-of-the-art baselines.

Critical strengths
  • A significant theoretical contribution is that the local summary size bounds are independent of the doubling dimension. This provides a clear theoretical and practical advantage over prior methods, such as Ceccarello et al. (2019), which suffer from exponential memory/space scaling as the doubling dimension increases.
  • Extending the framework to fairness constraints using LP-guided filtering and maximum-weight bipartite b-matching provides a rigorous structural solution to a complex problem. It directly addresses the dual constraints of strict group upper bounds and fractional coverage limits.
Critical weaknesses
  • The paper introduces both an unconstrained algorithm (Alg. 1) and a fair algorithm (Alg. 2 and 3). Furthermore, the baselines list YUAN-DIST as a point of comparison for the fair k-center clustering problem. However, the results presented in Figure 1 solely depict the unconstrained variant (OURALG-kCO) against unconstrained baselines (CPP19-Det, CPP19-Rand, Outliers-MR). The empirical evaluation of the fair framework appears to be missing or inadequately visualized.
  • The framework's ability to achieve (6+ϵ)(6+\epsilon) and (11+ϵ)(11+\epsilon) approximations relies heavily on geometric radius guessing. Because each worker must prepare and transmit capped summaries for H=O(1+ϵ−1log⁡(Rmax/Rmin))H=O(1+\epsilon^{-1}\log(R_{max}/R_{min})) radii, the communication cost and memory footprint could be large if the interval between RminR_{min} and RmaxR_{max} is large, which is not thoroughly analyzed in the text.
Questions for authors
  • How are RminR_{min} and RmaxR_{max} initialized in your experimental evaluations without incurring a massive upfront scan of the entire dataset? How sensitive are the actual communication overheads and memory usages to the size of HH in practice?
  • For the coordinator stage of the fair algorithm, you require solving LP (I) on the aggregated summaries. Given that the memory requirement scales with WoptW_{opt} (the peak workspace for LP representation), does solving this LP become a computational or memory bottleneck as the number of groups gg and machines mm scale up?
5 comments
AuthorsOpenReview ↗

Response to Reviewer yBzE

Thank you so much for recognizing the theoretical contributions and practical advantages of our framework for distributed kk-center clustering with outliers and its fair variant. We have submitted the manuscript with the appendix in this revision.

Q1. How are Rmin⁡R_{\min} and Rmax⁡R_{\max} initialized in your experimental evaluations without incurring a massive upfront scan of the entire dataset? How sensitive are the actual communication overheads and memory usages to the size of HH in practice?

Response. Thank you for raising this question. Our experimental implementation does not require an upper bound Rmax⁡R_{\max}. Your question also prompted us to revisit the original radius-guessing factor H=O(1+ε−1log⁡(Rmax⁡/Rmin⁡))H=O(1+\varepsilon^{-1}\log(R_{\max}/R_{\min})). We refined the procedure by selecting the local construction radius independently of the coordinator's coverage threshold. Each worker now uploads only one final summary, removing the multiplicative HH factor from communication and aggregated-summary storage.

Parallel stage. For the ordinary problem, partitions with ∣Pi∣≤k+z|P_i|\le k+z are uploaded directly with Ri=0R_i=0. Otherwise, worker ii selects Qi⊆PiQ_i\subseteq P_i with ∣Qi∣=k+z+1|Q_i|=k+z+1 and initializes Ri←1/2min⁡u,v∈Qi,u≠vd(u,v)R_i\gets 1/2 \min_{u,v\in Q_i, u\ne v}d(u,v), where Qi⊆PiQ_i\subseteq P_i with ∣Qi∣=k+z+1|Q_i|=k+z+1; It then increases the radius geometrically until the constructed summary satisfies ∣Si∣≤k(z+1)+z|S_i|\le k(z+1)+z. Only the final successful summary SiS_i and its radius RiR_i are uploaded.

Coordinator stage. The coordinator fixes S=⋃iSiS=\bigcup_iS_i and starts its search at R=max⁡iRiR=\max_iR_i. It increases the radius until the greedy trial returns ∣C∣≤k|C|\le k and ∣U∣≤z|U|\le z. All trials use the fixed received summaries and require no additional worker communication.

The fair variant follows the same principle, additionally preserving same-group candidates, using the cap ∣Si∪Ti∣≤k(z+g+1)+z|S_i\cup T_i|\le k(z+g+1)+z, and testing LP feasibility at the coordinator.

We have updated Algorithms 1–3, the approximation analyses supporting Theorems 4 and 12, and the associated communication and memory bounds accordingly.


Q2. For the coordinator stage of the fair algorithm, you require solving LP (I) on the aggregated summaries. Given that the memory requirement scales with WoptW_{\mathrm{opt}} (the peak workspace for LP representation), does solving this LP become a computational or memory bottleneck as the number of groups gg and machines mm scale up?

Response. Yes, solving the LP (I) at the coordinator can become a computational and memory bottleneck as mm and gg increase.

For memory bottleneck, using a dense primal-dual interior-point implementation, the space complexity (and hence the workspace bound) can be measured in arithmetic storage units as below: W=O((∣S∣+∣T∣+g)2)=O(m2Lf2)W=O\bigl((|S|+|T|+g)^2\bigr)=O(m^2L_f^2), where Lf=k(z+g+1)+zL_f=k(z+g+1)+z, S=⋃iSiS=\bigcup_i S_i is the aggregated witness set, T=⋃iTiT=\bigcup_i T_i is the aggregated candidate-center set, and gg is the number of demographic groups. Thus, the total memory bound is O(max⁡{n/m,mLf+W})O\left(\max\{n/m,mL_f+W\}\right). We have updated Theorem 12 to include WW, accounting for the additional coordinator workspace required for LP representation and optimization.

Dear Reviewer yBzE,

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 yBzE,

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 humbly request your feedback on our rebuttal. We would be happy to address any further questions or concerns. Thanks a lot.

Best regards,

The Authors of Submission 5793

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of Responses to the Reviewers

Dear Area Chair and Reviewers,

We sincerely thank the AC for overseeing the review process and the reviewers for their careful reviews and constructive feedback. In particular, we thank reviewer er3i for the continued discussion and for raising additional questions that allowed us to provide further clarifications. We have revised the manuscript and provided responses to the weaknesses and questions raised by each reviewer.

The main concern raised by the reviewers is the novelty of our results. We therefore briefly summarize our novelty below.

Our work provides two main results for distributed kk-center with outliers and its fair variant. For DkCO, we improve the approximation factor from 13+ε13+\varepsilon to 6+ε6+\varepsilon, at the cost of an explicitly quantified increase in communication. For DFkCO, we remove the exponential dependence on the doubling dimension from the communication bound while satisfying both the fairness constraints and the prescribed outlier budget. We have clarified these trade-offs and added a detailed comparison with previous work, including Malkomes et al., Li and Guo, Guha et al., Ceccarello et al., Huang et al., and related fair clustering methods.

We have also responded in detail to other concerns, including: (1) adding and enhancing experiments to demonstrate scalability and running time; (2) explaining how our algorithm handles the unknown optimal radius while preserving the communication-round complexity; (3) expanding the experimental discussion to provide more evidence of empirical performance and comparisons with prior work; (4) adding discussion of the fair variant and its dimension dependence; and (5) improving the related-work section and presentation.

We sincerely appreciate the reviewers' comments and hope that these responses, together with the revised manuscript, address their concerns.

AuthorsOpenReview ↗

Rebuttal Summary after Reviewer-Author Discussion Period

Dear AC and reviewers,

We sincerely thank the Area Chair and all reviewers for their constructive feedback. We have addressed the main concerns through additional analysis, detailed clarifications, and manuscript revisions. The changes are highlighted in green. We respectfully draw your attention to the following points.

  • Distributed kk-center with outliers (D$k$CO). Our algorithm improves the approximation factor from 13+ε13+\varepsilon to 6+ε6+\varepsilon, at the cost of increasing the communication bound from O(m(k+z))O(m(k+z)) to O(mkz)O(mkz).

  • Distributed fair kk-center with outliers (DF$k$CO). Our extension removes the exponential dependence on the doubling dimension DD from the communication bound, reducing it from O(mk(k+z)(c/ε)D)O(mk(k+z)(c/\varepsilon)^D) to O(mk(z+g))O(mk(z+g)), at the cost of increasing the approximation factor from 3+ε3+\varepsilon to 11+ε11+\varepsilon.

  • Experimental results. Across the reported D$k$CO configurations, cost reductions relative to the lowest baseline mean cost in each configuration range from 4.32% to 17.05%, with an average reduction of 9.80%. The DF$k$CO experiments also show improvements over the baselines.

  • Reviewers’ assessments. All reviewers gave our paper the highest score for Soundness. Reviewers W4Pm and er3i also gave it the highest score for Presentation (3/3) and scored it 2/3 for Informativeness. We appreciate these favourable assessments and respectfully ask that they be taken into account when reconsidering the overall rating.

We believe these theoretical and empirical results demonstrate the value of our contributions to both problems. We hope our rebuttal and revised manuscript support a favourable final assessment.

Thank you again for your time and consideration.

Best regards,

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.