acceptodds
Under review as a conference paper at ICLR 2027

Improved Approximation Algorithms for Euclidean Fair -Center Clustering

Abstract

Let be a set of points partitioned into demographic groups. Given an upper bound on the number of centers that can be chosen from each group , the fair -center problem asks for a set of centers that satisfies these fairness constraints while minimizing the maximum distance from any point to its nearest center. In this paper, we first present a randomized algorithm for the Euclidean setting that achieves an approximation ratio of , thereby breaking the factor- barrier known for general metrics. The key idea is to reduce the problem to a generalized exact matching problem on a carefully designed auxiliary graph, which can then be solved using a generalized exact matching algorithm. For the case , we then develop a deterministic algorithm with the same approximation ratio and improved running time. This algorithm exploits the geometric structure of the Euclidean setting, allowing us to use maximum matching rather than exact matching. To the best of our knowledge, this is the first approximation ratio strictly below for Euclidean fair -center, suggesting that fair -center admits better approximation guarantees in Euclidean spaces. Finally, we complement our theoretical results with experiments on five real-world datasets and one synthetic dataset with known optimal solutions, demonstrating the improvements in clustering utility over state-of-the-art methods.

Primary area:
optimization
Keywords:
Clustering, fair $k$-center, geometry

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_16LeOpenReview ↗
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
AuthorsOpenReview ↗

Responses to Reviewer 16Le (Part I)

Thank you for your valuable comments, particularly your suggestions for improving the experimental section.

W1. Claims in the Abstract to provide the first approximation ratio strictly below 3 for Euclidean fair kk-center while citing a 2026 paper in the bibliography that already attained that.

Response. Thank you for pointing out this ambiguity. Lin et al. (2026) indeed achieve an approximation ratio below 33 through a parameterized algorithm, whose running time remains exponential in kk even when m=2m=2.

Our contribution is to achieve a ratio below 33 in polynomial time: deterministically when m=2m=2, and with randomization for any fixed mm. To the best of our knowledge, our deterministic algorithm is the first polynomial-time algorithm achieving an approximation ratio strictly below 33 for Euclidean fair kk-center with m=2m=2. We have revised the abstract and contribution statements to make this distinction explicit.

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 kk-supplier problems. There is little novelty in transferring this to fair kk-center via known matching formulations.

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 kk-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=2m=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 Γ\Gamma), 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.

W3. The algebraic matching algorithm is computationally prohibitive for realistic group counts.

Response. You are absolutely right that the algebraic algorithm can become computationally expensive as mm increases. Its polynomial-time guarantee applies to fixed mm, 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 55-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=2m=2, our deterministic algorithm avoids the algebraic matching routine entirely and runs in O(kn2)O(kn^2) time. We have supplemented the experimental discussion with memory measurements to make the limitations of the randomized implementation more transparent.

AuthorsOpenReview ↗

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 (1+3)(1+\sqrt{3}) guarantee through a parameterized algorithm whose running time remains exponential in both kk and mm (and hence exponential in kk even for m=2m=2). Our randomized algorithm is polynomial in nn and kk for every fixed mm, while our deterministic algorithm provides the same guarantee in polynomial time when m=2m=2.

The following table compares the offline algorithms achieving the (1+3)(1+\sqrt{3}) guarantee. All methods assume Euclidean distances and disjoint groups.

MethodGroup assumptionsApproximation ratioRunning-time bound
Lin et al. (2026), parameterized algorithmArbitrary mm1+31+\sqrt{3}2O(klog⁡(m+1))poly⁡(n,k,m)2^{O(k\log(m+1))}\operatorname{poly}(n,k,m)
Our randomized algorithmAny fixed mm1+31+\sqrt{3}Om(nk2+km+6)O_m(nk^2+k^{m+6})
Our deterministic algorithmm=2m=21+31+\sqrt{3}O(kn2)O(kn^2)

Here, nn is the number of input points and k=∑i=1mkik=\sum_{i=1}^{m}k_i. The notation OmO_m allows the hidden constant to depend on the fixed number of groups mm. 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 m=4m=4 & m=5m=5 on the Adult dataset? At what value of mm 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 (m=5m=5). Figure 7 reports the running time of our algorithm for this setting (m=5m=5).

The Adult dataset occupies approximately 4 MB. For the Adult–Race setting with m=5m=5, 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 k=100k=100 under an 8 GB memory limit:

Number of groups (mm)Memory usage
5584.5 MiB
106859.1 MiB
157469.5 MiB
20Out of memory

These measurements show the memory requirements for the larger tested values of mm. The increase is particularly pronounced between m=5m=5 and m=10m=10, while memory usage remains high at m=15m=15. Among the tested settings, the first out-of-memory failure occurred at m=20m=20.

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 kk fixed at 100100.

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

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

This paper studies fair k center problem in Euclidean space, where the amount of centers in each color has an upper bound. This paper proposes a simple algorithm, that transform the original problem to a perfect matching in a auxiliary graph, which can be done in O(n2)O(n^2) time. The claimed approximation ratio is 1+31+\sqrt{3}, surpass the previous 33-approximation. They also provide a faster deterministic algorithm for 2 colors case. Finally, they design experiments to test the proposed algorithm with related baselines.

Critical strengths

The problem they study is classic. The proposed result improves the state-of-the-art theoretical bound. Both theoretical and practical parts are solid, clear, easy to follow.

Critical weaknesses
  1. One critical idea of beating 33-approximation, unit ball in Euclidean covers at most two 3\sqrt{3}-net points, is borrowed from the previous work, e.g, (Nagarajan et al. 2020) used the same idea to get a (1+3)(1+\sqrt{3})-approximation for Euclidean kk-supplier problem.
  2. Compared to previous work, the scope of this paper is narrower. The proposed algorithm works only for Euclidean space with fixed number of groups (if we require polynomial time). For instance, (Chen et al. 2016) studied a series of cover problems (including fair k center) in general matric space, and (Jones et al. 2020)'s method works for general number of groups.
  3. There are several typos in Definition 2 that should be corrected. (1) Page 4, Line 163, "and k2k_2" should be removed; (2) Line 164, there should be a "==" between "PP" and "∪j\cup_j"; (3) Line 168, "∣C∩P∣|C\cap P|" should be "∣C∩Pj∣|C\cap P_j|".
Questions for authors
  1. What is the barrier of generalizing this algorithm to general metric space and general mm.
  2. What is the time complexity of the randomized algorithm is Section 3? Is the number of groups mm put in the exponential part of the time complexity? It is encouraged to give a explicit time complexity analysis in the main text.
  3. It is encouraged to add one formal statement (a theorem) to summarize the approximation and running time in Section 3. Current text structure may mislead reader to believe 1+31+\sqrt{3} works only for m=2m=2.
4 comments
AuthorsOpenReview ↗

Responses to Reviewer EKr3 (Part I)

Thank you for your detailed comments and valuable suggestions, which have helped us improve the paper.

W1. One critical idea of beating 3-approximation, unit ball in Euclidean covers at most two 3\sqrt{3}-net points, is borrowed from the previous work, e.g., (Nagarajan et al. 2020) used the same idea to get a (1+3)(1+\sqrt{3})-approximation for Euclidean kk-supplier problem.

Response. Thank you for highlighting this connection. You are absolute right that the geometric property in Lemma 1 is due to Nagarajan et al. (2020), as we explicitly acknowledge their contribution. We would like to clarify the additional ideas needed to handle the group-wise fairness constraints.

First, for any fixed mm, we construct a reduction to colored budgeted perfect matching that encodes both the coverage requirement and all group budgets. Although the geometric property provides the starting point, incorporating the fairness constraints requires a different matching formulation and a proof of the correspondence between feasible covers and matchings.

Second, for m=2m=2, our deterministic algorithm establishes a stronger property of the specially constructed residual instance. Specifically, Lemma 5 shows that every unit ball centered at a second-group point contains at most one residual representative. Together with our preprocessing, this property allows the remaining selection problem to be solved using ordinary maximum matching, avoiding the randomized constrained-matching routine. The proof of this additional geometric property appears in Appendix A.4.

We will revise the presentation to distinguish more clearly between the geometric ingredient inherited from prior work and our new reductions and residual-instance analysis.

W2. Compared to previous work, the scope of this paper is narrower. The proposed algorithm works only for Euclidean space with fixed number of groups (if we require polynomial time). For instance, (Chen et al. 2016) studied a series of cover problems (including fair k center) in general matric space, and (Jones et al. 2020)'s method works for general number of groups.

Response. We agree that our polynomial-time guarantees concern a more specialized setting. Our contribution is to exploit this setting to obtain a stronger approximation guarantee while satisfying all group budgets.

The Euclidean setting is directly relevant to established applications of fair data summarization. For example, Kleindessner et al. (ICML 2019) use Euclidean distances between image feature vectors for fair image summarization. Similarly, Angelidakis et al. (ICML 2022) represent Adult census records as numerical feature vectors and use Euclidean distance for fair data summarization.

The fixed-mm setting is also practically relevant when fairness is specified using an attribute with a small number of categories, such as the two-group Sex and five-group Race settings in our experiments.

Within this setting, our randomized algorithm improves the polynomial-time approximation guarantee from 33 to 1+31+\sqrt{3} for any fixed mm. Moreover, when m=2m=2, we obtain a deterministic polynomial-time algorithm with the same guarantee. Unlike the prior FPT (1+3)(1+\sqrt{3})-approximation of Lin et al. (2026) with a runtime exponential in kk, our algorithms is with a polynomial runtime and does not need fixed kk. We will clarify these distinctions and explicitly state the dependence on mm.

W3. There are several typos in Definition 2 that should be corrected. (1) Page 4, Line 163, "and k2k_2" should be removed; (2) Line 164, there should be a "==" between "PP" and "∪j\cup_j"; (3) Line 168, "∣C∩P∣|C\cap P|" should be "∣C∩Pj∣|C\cap P_j|".

Response. Thank you for identifying these typos. We have corrected all three errors and highlighted the corresponding changes in the revised manuscript. We have also checked the manuscript for similar issues.

AuthorsOpenReview ↗

Responses to Reviewer EKr3 (Part II)

Questions for Authors

Q1. What is the barrier of generalizing this algorithm to general metric space and general mm.

Response. The two extensions face different limitations.

For general metric spaces, the geometric properties underlying Lemmas 1 and 5 need not hold. In particular, a unit ball can contain arbitrarily many 3\sqrt{3}-separated representatives. A candidate center may therefore cover more than two representatives, so its coverage can no longer be encoded by a single graph edge. Consequently, our matching reduction does not directly extend to general metrics.

For arbitrary mm, our randomized reduction remains valid, but its running time is no longer guaranteed to be polynomial. The algebraic matching routine incurs a dependence exponential in mm, as made explicit in Q2 below. This is a limitation of our current approach; we do not claim that such a dependence is unavoidable for every possible algorithm.

For the deterministic algorithm, the additional residual-instance structure established for m=2m=2 is what permits the use of ordinary maximum matching. We do not currently have an analogous reduction for more groups.

Q2. What is the time complexity of the randomized algorithm is Section 3? Is the number of groups mm put in the exponential part of the time complexity? It is encouraged to give a explicit time complexity analysis in the main text.

Response. Thank you for this suggestion. Yes, the running-time bound has an exponential dependence on mm.

Let n=∣S∣n=|S| and k=∑i=1mkik=\sum_{i=1}^{m}k_i. Assuming that the optimal radius is known, a conservative bound for the full-degree interpolation implementation is

O(nk2+mk6(2k+1)m)O\left(nk^2+mk^6(2k+1)^m\right)

finite-field arithmetic operations. With a suitable field size, the algorithm succeeds with probability at least 1−δ1-\delta, for any prescribed δ∈(0,1)\delta\in(0,1). The failure probability affects the required field size and hence the bit complexity.

Thus, the running time is polynomial in nn and kk for every fixed mm, but may grow exponentially when mm varies. We will state the bound, the success probability, and the known-radius assumption explicitly in Section 3, with the detailed analysis in Appendix C.

Q3. It is encouraged to add one formal statement (a theorem) to summarize the approximation and running time in Section 3. Current text structure may mislead reader to believe 1+31+\sqrt{3} works only for m=2m=2.

Response. Thank you for this helpful suggestion. We will add a formal theorem in Section 3 stating the randomized algorithm's (1+3)(1+\sqrt{3}) approximation guarantee, success probability, running time, and assumptions. We will explicitly clarify that the randomized guarantee holds for any fixed number of groups mm, whereas the deterministic algorithm with running time O(kn2)O(kn^2) applies to m=2m=2.

Thanks for the detailed response. I will remain my rating.

Thank you for your reply and for recognizing our theoretical contribution. We would be very happy to provide any further clarification or address any follow-up questions you may have.

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

This paper considers the fair k-center problem. Here there is a set of points P which is partitioned into m sets, P_1 , ... P_m. We are further given k_1 , ... k_m (k=\sum_i k_i) . The goal is to pick k_i points from P_i such that the k-center cost is minimized (the cost is the same as the standard uncolored version).

The uncolored version has a factor 2 approximation. The colored problem in general metrics has approximation factor of 3. This paper considers the problem in the Euclidean setting and gives a randomized 1+\sqrt(3) approximation for the problem. However the main downside is that the running time of the algorithm is polynomial only when m is fixed. Otherwise as mentioned in appendix C, the runtime has \prod_i (k_i+1) in it which scales poorly with the number of groups and their budgets.

They also give a deterministic algorithm for the case of m=2.

They further run experiments comparing their algorithms with prior work.

The papers technique is to first impose a net on the set of points and set the goal as to cover all the net points. The parameters are set so that no candidate can cover more than two points from the net. Candidate centers can therefore be encoded as edges covering pairs. This can reduce the problem to the colored budgeted perfect matching.

Critical strengths

The problem is relevant to ICLR's interests in clustering and algorithmic fairness.

The experiments include relevant fair baselines.

Critical weaknesses

The contribution of the paper is not sufficient for ICLR. In particular there already exists a 3 approximation for general metric spaces. Further there is already an algorithm getting the approximation factor of 1+\sqrt(3) for the euclidean case which is parameterized by k and m. This paper makes the algorithm polynomial in k for fixed m, however it has substantial dependence on the group budgets, limiting its scalability.

Questions for authors

Are there any lower bounds justifying the dependence on m and the group budgets?

1 comment
AuthorsOpenReview ↗

Responses to Reviewer 1Dir

Thank you for your valuable comments and for the time and effort you have devoted to reviewing our manuscript.

W1-1. The contribution of the paper is not sufficient for ICLR. In particular there already exists a 3 approximation for general metric spaces.

Response. Our main contribution is to obtain an approximation ratio below 33 in polynomial time by exploiting Euclidean geometry. For fair kk-center in general metrics, no polynomial-time (3−ε)(3-\varepsilon)-approximation exists unless P=NP\mathsf{P}=\mathsf{NP}, even when m=2m=2 (Thejaswi, 2026). Our deterministic (1+3)(1+\sqrt{3})-approximation for m=2m=2 therefore establishes a separation in polynomial-time approximability between the Euclidean and general metric settings. By comparison, standard kk-center admits a 22-approximation in general metrics, while obtaining a polynomial-time (2−ε)(2-\varepsilon)-approximation in Euclidean space, even in the plane, remains a longstanding open problem. Moreover, for any fixed mm, we obtain the same (1+3)(1+\sqrt{3}) approximation guarantee with a randomized polynomial-time algorithm.

Euclidean space is also an important setting for machine learning and data mining. Embedding methods such as node2vec, UMAP, and DeepWalk produce vector representations, to which our setting applies when Euclidean distance is used. More directly related to our problem, Kleindessner et al. (ICML 2019) use Euclidean distances between image feature vectors for fair image summarization. Similarly, Angelidakis et al. (ICML 2022) represent Adult census records as numerical feature vectors and use Euclidean distance for fair data summarization.

Therefore, we believe that our randomized and deterministic algorithms together constitute an important contribution.

W1-2. Further there is already an algorithm getting the approximation factor of 1+31+\sqrt3 for the euclidean case which is parameterized by kk and mm. This paper makes the algorithm polynomial in kk for fixed mm, however it has substantial dependence on the group budgets, limiting its scalability.

Response. Our improvement over Lin et al. (IJCAI 2026) is that the same approximation ratio becomes attainable in polynomial time for fixed mm, with a deterministic algorithm for m=2m=2.

  1. For m=2m=2, we provide a deterministic (1+3)(1+\sqrt{3})-approximation algorithm with running time O(kn2)O(kn^2) under the known-radius assumption used in our analysis. In contrast, the previous algorithm has a running time exponential in kk, even when m=2m=2. Our algorithm removes this exponential dependence while retaining the same approximation guarantee.

  2. For fixed mm, the budget-dependent factor in our randomized algorithm is ∏i=1m(ki+1)\prod_{i=1}^{m}(k_i+1). Since ki≤kk_i\le k, this factor is at most (k+1)m(k+1)^m and is therefore polynomial in kk for every fixed mm. We acknowledge that this dependence can become expensive when mm is large. However, applications naturally arise with a small number of groups. For example, the binary gender setting studied by Kleindessner et al. (2019) has m=2m=2.

Q1. Are there any lower bounds justifying the dependence on mm and the group budgets?

Response. We do not establish a lower bound showing that the dependence on mm or the group budgets is necessary for Euclidean fair kk-center. This dependence arises from our current algebraic algorithm for colored budgeted matching. Classical exact matching admits randomized polynomial-time algorithms, while finding a deterministic polynomial-time algorithm remains a longstanding open problem (Murakami and Yamaguchi, 2025). However, our reduction from clustering to matching does not establish a corresponding hardness result for clustering or show that the budget dependence is unavoidable. Thank you for raising this question. We thank the reviewer for pointing out that improving this dependence is an important direction for future work.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of Contributions and Responses to Reviewers

Dear Area Chair,

Thank you for overseeing the review process. We appreciate the three reviewers’ comments and would like to summarize our responses to their main concerns regarding the contribution, technical novelty, and scalability.

1. Contribution and comparison with prior work.

Our main contribution is to obtain a (1+3)(1+\sqrt{3})-approximation for Euclidean fair kk-center in polynomial time: deterministically when m=2m=2, and with randomization for any fixed mm. The deterministic algorithm runs in O(kn2)O(kn^2) time under the known-radius assumption used in our analysis.

We acknowledge that Lin et al. (IJCAI 2026) previously achieved the same approximation ratio through a parameterized algorithm. The distinction is that their running time remains exponential in both kk and mm (and hence remains exponential even when m=2m=2), whereas our algorithms do not require kk to be fixed. We have revised the abstract and contribution statements to make this distinction explicit and provided a comparison table in our rebuttal.

The deterministic result also establishes a separation in polynomial-time approximability: in general metrics, a (3−ε)(3-\varepsilon)-approximation is NP-hard even for two groups (Thejaswi, 2026), whereas our Euclidean algorithm achieves 1+3<31+\sqrt{3}<3.

2. Technical novelty beyond the inherited geometric lemma.

We have explicitly credited Nagarajan et al. (2020) for the geometric property in Lemma 1 in the original manuscript. Our contribution builds on this property to further enforce the group-wise fairness budgets, which an unconstrained matching covering all representatives need not satisfy.

For the randomized algorithm, we construct and prove a reduction to colored budgeted perfect matching that simultaneously encodes coverage and all group budgets. For the deterministic algorithm, our preprocessing yields a stronger residual-instance property, proved in Lemma 5: every unit ball centered at a second-group point contains at most one residual representative. This additional structure enables a reduction to ordinary maximum matching, avoiding the randomized algebraic routine.

3. Parameter dependence, assumptions, and presentation.

We have clarified that the randomized algorithm is polynomial in nn and kk for each fixed mm, while its running time can grow exponentially as mm varies. Our rebuttal explicitly states the running-time bound, success probability, and known-radius assumption. We have consolidated these guarantees in a formal theorem in Section 3 to distinguish the fixed-mm randomized result from the deterministic m=2m=2 result. We have also corrected the identified typos in Definition 2.

4. Practical relevance and scalability evidence.

Small-group settings arise in established fair data summarization applications, including the two-group Sex and five-group Race settings addressed in previous papers. We reported end-to-end runtimes in Figure 7 and supplemented the discussion with memory measurements. For Adult–Race (m=5m=5), the matrix and computational workspace used an average of 25.75 MB. In synthetic experiments with k=100k=100 under an 8 GB memory limit, memory usage increased substantially, and the first failure among the tested settings occurred at m=20m=20. We present these results as evidence of the implementation’s practical limits. For m=2m=2, our deterministic algorithm avoids the algebraic routine entirely.

We hope these clarifications help assess the polynomial-time contribution and its scope. Thank you for your consideration; we would be happy to address any further questions.

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 carefully addressed the major concerns through additional experiments, detailed clarifications, and manuscript revisions (highlighted in blue). Below, we focus on the two issues that received the most attention.

1. Significance compared with prior work

We achieve the approximation ratio of 1+3<31+\sqrt{3}<3 for Euclidean fair kk-center in randomized polynomial time for any fixed mm and in deterministic polynomial time for m=2m=2. This is the first ratio smaller than 3 with polynomial runtime. In comparison, Lin et al. (IJCAI 2026) previously achieved the same approximation ratio but with runtime exponential in both mm and kk.

Our results demonstrate that Euclidean fair kk-center admits a strictly better polynomial-time approximation guarantee than its general-metric counterpart (1+3≈2.7321+\sqrt{3}\approx 2.732 versus 33). This separation is particularly notable in light of classical kk-center. For the unconstrained problem, the optimal polynomial-time approximation ratio is 22 in general metrics unless P=NP\mathrm{P}=\mathrm{NP}, and 22 remains the best-known approximation ratio even in the Euclidean plane.

2. Technical novelty

We appreciate that the reviewers recognized the merits of our deterministic algorithm during the discussion. We would be grateful if this contribution were taken into account in the final assessment.

For the randomized algorithm with fixed mm, we use the geometric property of Nagarajan et al. (2020) as a starting point and construct an auxiliary graph that novelly encodes how each candidate center can cover one or two representatives and which group budget it uses. This construction reduces the problem of covering all representatives under the group budgets to finding a perfect matching that respects the edge-color budgets. We then extend algebraic exact matching techniques to solve the resulting instance.

We believe these clarifications address the remaining concerns about the significance and technical novelty of our results. We hope our rebuttal and revised manuscript support a favorable 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.