- Rating
- 2(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This manuscript investigates Fair k-Center (FkC) clustering in d-dimensional Euclidean space, with points partitioned into m demographic groups and with individual group center budgets k_i (k = \sum_i k_i).
In general metric spaces, fair k-center admits an approximation barrier of 3. This paper proposes a randomized algorithm for Euclidean spaces with approximation ratio of 2.73 for any fixed m.
The algorithm computes a \sqrt{3}-separated independent set and uses a guarantee from Nagarajan et al. (2020) that any unit ball contains at most two points from it. Which reduces center selection to colored budgeted perfect matching on an auxiliary graph, which is solved using algebraic randomized matching via Tutte matrices (Mulmuley et al., 1987).
For m=2, the paper presents a deterministic algorithm (with the same approximation) based on maximum matching.
Experiments are conducted on five real-world datasets and one synthetic dataset.
Critical strengths
Unlike the FPT algorithm of Lin et al. (2026) which has exponential dependence on k, the proposed matching reductions achieve polynomial dependence on k when m is constant.
Critical weaknesses
W1. Claims in the Abstract to provide the first approximation ratio strictly below 3 for Euclidean fair k-center while citing a 2026 paper in the bibliography that already attained that.
W2. Core technical reduction relies entirely on Lemma 1 from Nagarajan et al. (2020), which was already applied to achieve a similar bound in Euclidean k-supplier problems. There is little novelty in transferring this to fair k-center via known matching formulations.
W3. The algebraic matching algorithm is computationally prohibitive for realistic group counts.
Questions for authors
Q1. Why does the abstract state that this is the first approximation ratio below 3? Didn't Lin et al. (2026) achieve the same approximation? Could you provide a rigorous comparison table showing the asymptotic runtimes, assumptions, and parameter dependencies between your work and theirs?
Q2. What is the empirical runtime and memory usage of evaluating the Tutte matrix determinant for m=4 & m=5 on the Adult dataset? At what value of m does the algebraic algorithm run out of memory?
6 comments
Responses to Reviewer 16Le (Part II)
Questions for Authors
Q1. Why does the abstract state that this is the first approximation ratio below 3? Didn't Lin et al. (2026) achieve the same approximation? Could you provide a rigorous comparison table showing the asymptotic runtimes, assumptions, and parameter dependencies between your work and theirs?
Response. Thank you for this valuable suggestion. We agree that the original wording should explicitly distinguish parameterized and polynomial-time approximation algorithms.
Lin et al. (2026) achieve the same guarantee through a parameterized algorithm whose running time remains exponential in both and (and hence exponential in even for ). Our randomized algorithm is polynomial in and for every fixed , while our deterministic algorithm provides the same guarantee in polynomial time when .
The following table compares the offline algorithms achieving the guarantee. All methods assume Euclidean distances and disjoint groups.
| Method | Group assumptions | Approximation ratio | Running-time bound |
|---|---|---|---|
| Lin et al. (2026), parameterized algorithm | Arbitrary | ||
| Our randomized algorithm | Any fixed | ||
| Our deterministic algorithm |
Here, is the number of input points and . The notation allows the hidden constant to depend on the fixed number of groups . Our bounds follow the known-optimal-radius convention used in the analysis; radius-search overhead must be included separately. The randomized bound counts finite-field arithmetic operations.
We have revised the contribution statements to clarify that our novelty concerns polynomial-time approximation guarantees.
Q2. What is the empirical runtime and memory usage of evaluating the Tutte matrix determinant for & on the Adult dataset? At what value of does the algebraic algorithm run out of memory?
Response. In our real-world experiments, the number of groups is determined by the categories of the selected demographic attribute. As shown in Table 2, the Adult–Race setting contains five groups (). Figure 7 reports the running time of our algorithm for this setting ().
The Adult dataset occupies approximately 4 MB. For the Adult–Race setting with , the input matrix and computational workspace together used an average of 25.75 MB of memory.
To further investigate memory usage as the number of groups increases, we conducted experiments on synthetic data with under an 8 GB memory limit:
| Number of groups () | Memory usage |
|---|---|
| 5 | 584.5 MiB |
| 10 | 6859.1 MiB |
| 15 | 7469.5 MiB |
| 20 | Out of memory |
These measurements show the memory requirements for the larger tested values of . The increase is particularly pronounced between and , while memory usage remains high at . Among the tested settings, the first out-of-memory failure occurred at .
We attribute this growth to the algebraic matching routine and its Pfaffian-based self-reduction, consistent with the parameter dependence in our analysis. These results demonstrate that memory consumption can become a practical limitation as the number of groups increases, even with fixed at .
Dear Reviewer 16Le,
Thank you for your review.
Authors have responded.
As the rebuttal period nears its end, could you please let us know whether the authors' response addresses your main concerns? Also, would you consider updating your rating based on the response? If not, what is your main remaining concern?
Your feedback would be appreciated.
Regards, AC
Responses to Reviewer 16Le (Part I)
Thank you for your valuable comments, particularly your suggestions for improving the experimental section.
Response. Thank you for pointing out this ambiguity. Lin et al. (2026) indeed achieve an approximation ratio below 3 through a parameterized algorithm, whose running time remains exponential in k even when m=2.
Our contribution is to achieve a ratio below 3 in polynomial time: deterministically when m=2, and with randomization for any fixed m. To the best of our knowledge, our deterministic algorithm is the first polynomial-time algorithm achieving an approximation ratio strictly below 3 for Euclidean fair k-center with m=2. We have revised the abstract and contribution statements to make this distinction explicit.
Response. We agree that Lemma 1 is inherited from Nagarajan et al. (2020), and we explicitly acknowledge their work. However, extending this geometric ingredient to fair k-center requires more sophiscated ideas to enforce the group-wise budgets. In particular, a matching that covers all representatives can still violate the fairness constraints.
For our randomized algorithm, we construct a reduction to colored budgeted perfect matching that encodes both coverage and all group budgets, and prove the correspondence between feasible covers and matchings.
Moreover, our deterministic algorithm for m=2 is a separate main contribution. Through preprocessing, we obtain a residual instance with the stronger geometric property established in Lemma 5: every unit ball centered at a second-group point contains at most one residual representative (ie., points of Γ), rather than two. Together with the residual-instance structure, this property allows us to solve the remaining selection problem using ordinary maximum matching, avoiding the randomized algebraic routine.
We respectfully ask that the contribution be assessed through both the budget-preserving reduction and the additional geometric analysis enabling the deterministic algorithm.
Response. You are absolutely right that the algebraic algorithm can become computationally expensive as m increases. Its polynomial-time guarantee applies to fixed m, and its practical scalability to many groups is a limitation.
Nevertheless, small numbers of groups arise in established applications. For example, Kleindessner et al. (ICML 2019) explicitly study the two-group setting (for male and female) and provide a dedicated 5-approximation algorithm. Angelidakis et al. (ICML 2022) also evaluate their method on the Diabetes dataset using two demographic groups. Our experiments similarly include the two-group Sex and five-group Race settings.
Furthermore, for m=2, our deterministic algorithm avoids the algebraic matching routine entirely and runs in O(kn2) time. We have supplemented the experimental discussion with memory measurements to make the limitations of the randomized implementation more transparent.