"Weakness: The centroid set-based algorithm is specific to the Euclidean setting and cannot be extended to general metric spaces."

Thanks for this question. It is true that the approximate centroid set can only be obtained in Euclidean space. In metric space, we usually assume that the potential facility set is given and its size is assumed to be polynomial in $n$. Under this assumption, our algorithm can be extended to general metric spaces. We use the given potential facility set as our candidate set, and we use the triangle inequality, i.e., $dist(a,b) \le dist(a,c) + dist(b,c)$, to replace Proposition 1. We can also obtain $(1+2\rho)$-approximate solution for fair $k$-median and ($2+8\rho)$-approximation of fair $k$-means in metric space. The detailed proof is provided in Appendix E of our revised paper.

Finally, we would like to emphasize that the major bottleneck of our approach for non-Euclidean space is the lack of the centroid set for them. If such a centroid set (or some similar structure) is available, we can immediately improve the approximation factor for those cases. A highlight of our current paper is that it brings a new perspective to fair clustering problems, which comes from this classical geometric structure. We hope that our work could inspire more improvements to fair clustering in future.

"Weakness: The exponential dependence of the running time on d may be problematic for high-dimensional data." and "Weakness: PTAS for vanilla k-means either have exponential dependence on k or d. So, the ~ 5-approximation is at the cost of increasing the running time."

We agree with the reviewer. In theory, the exponential dependence of the running time on $d$ arises from the inherent hardness of vanilla $k$-means. Even when $d$ is constant, the vanilla $k$-means problem remains NP-hard [1]. Hence, handling $k$-means in high-dimensional space is even more challenging. We agree that the PTAS algorithm is expensive. However, in practice, we can use $k$-means++, which is a popular method for solving the $k$-means problem and can be efficiently implemented. In our experiment, we demonstrated that using $k$-means++ can still achieve better performance than the baselines in most cases. In general, our algorithm does take higher running time for achieving the better clustering cost. In our comparison experiment, the running time of our algorithm is acceptable. Please refer to Appendix F.6 in our revised paper for a detailed discussion.

[1] Mahajan M, Nimbhorkar P, Varadarajan K. The planar k-means problem is NP-hard[J]. Theoretical Computer Science, 2012, 442: 13-21.

"Weakness : The techniques have mainly been borrowed from previous works. So, the theoretical contribution has limited novelty." and "Similar ideas have been used in the past (see, e.g., [A]),..."

Thank you for providing reference [A]. We have carefully read the discussion on the $k$-median problem in that paper, including Theorem 4 mentioned by the reviewer. We agree that their framework is somewhat similar with our “relax and merge” framework at first glance, but we also would like to emphasize the important differences between them.

• First, the algorithm of [A] is not easy to extend to address the fair $k$-means problem. [A] mainly focuses on the $k$-median problem in data streams. However, it is non-trivial to extend their method to solve the fair $k$-means problem. The major obstacle is how to maintain the fairness constraints inside their framework. In particular, a key challenge is to guarantee the partition and merge processes do not cause too much cumulative error regarding the fairness constraint.

• Moreover, even if the method of [A] was able to be extended to our setting, the claimed approximation ratio of [A] would be higher than ours. In [A], the claimed ratio is $2c(1 + 2b) + 2b$, where $b$ and $c$ are the approximation ratios of $k$-clustering algorithms in two stages, while ours provides a $(1+4\rho)$ approximation factor. In addition, there are also several technical differences between the objectives of “k-means” and “k-median”.

Nevertheless, we appreciate the reviewer for letting us know the work [A]. As we mentioned in our title, our two-step framework is "simple" yet "effective." We believe that this framework has potential to extend to other scenarios, such as in data streams, which is the major setting of [A]. We thank the reviewer for providing us with instructive material. We are glad to explore whether our framework can also be extended to a streaming fashion.

Finally, we also want to mention that our contributions are not only the "relax and merge" approach, but also the establishment of a connection between the approximate centroid set and the fair $k$-means problem, which provides a new perspective for addressing fair clustering. We hope this new perspective could inspire more improvements to fair clustering in future. In addition, to address the unique “rounding” requirement of fair clustering (that not appears in ordinary k-clustering), our algorithms also combine several other key techniques.

"Q1: Can one extend the results to the fair $k$-median?"

Thanks for this question. Although the focus of our paper is mainly about k-means in Euclidean space, it is also deserved to provide the discussion for possible extensions. We need to discuss this issue separately for different scenarios.

If we consider the $k$-median problem in Euclidean space, where facilities can lie in the ambient space, an immediate question is how to obtain a candidate set. In $k$-means, we have the method of [Matousek (2000)] to provide an "approximate centroid set". However, for $k$-median, as far as we know there is currently no method to construct such a candidate set to cover all potential optimal facilities. We would like to list it as an important open problem deserved to study in future.

If we consider the $k$-median problem in general metric space or in Euclidean space but with a potential facility set whose size is polynomial and given, our framework can be extended to address this issue. We just directly use the whole facility set as our candidate set. As for the analysis, although we cannot use Proposition 1 to handle the $k$-median problem, we can use the triangle inequality instead. By doing so, we get a weaker upper bound of the approximation ratio compared with our result for Euclidean k-means -- $(1+2\rho)$ for the $k$-median problem, where $\rho$ is the approximation ratio for vanilla $k$-median. If the doubling dimension of metric space is fixed (this is a common assumption for some applications, since the doubling dimension measures data’s intrinsic dimension, which is usually low), then equipped with PTAS for vanilla $k$-median (such as the methods from [1, 2]), we can obtain a $3+\epsilon$-approximation for fair $k$-median. The detailed proof is provided in Appendix E of our revised paper.

Finally, we would like to emphasize that the major bottleneck of our approach for handling k-median and non-Euclidean space is the lack of the centroid set for them. If such a centroid set (or some similar structure) is available, we can immediately improve the approximation factor for those cases. A highlight of our current paper is that it brings a new perspective to fair clustering problems, which comes from this classical geometric structure. We hope that our work could inspire more improvements to fair clustering in future.

[1] Friggstad Z, Rezapour M, Salavatipour M R. Local search yields a PTAS for k-means in doubling metrics[J]. SIAM Journal on Computing, 2019, 48(2): 452-480.

[2] Cohen-Addad V, Feldmann A E, Saulpic D. Near-linear time approximation schemes for clustering in doubling metrics[J]. Journal of the ACM (JACM), 2021, 68(6): 1-34.

"Weakness 1: The running time of the first algorithm is exponential on d. Thus the result does not scale in high dimensions."

We agree with the reviewer. In theory, the exponential dependence of the running time on $d$ arises from the inherent hardness of vanilla $k$-means. Even when $d$ is constant, the vanilla $k$-means problem remains NP-hard [1]. Hence, handling $k$-means in high-dimensional space is even more challenging. However, in practice, we can use $k$-means++, which is a popular method for solving the $k$-means problem and can be efficiently implemented. In our experiment, we demonstrated that using $k$-means++ can still achieve better performance than the baselines in most cases.

[1] Mahajan M, Nimbhorkar P, Varadarajan K. The planar k-means problem is NP-hard[J]. Theoretical Computer Science, 2012, 442: 13-21.

I have read the feedback and other reviews. I will keep my rating on this paper.

"Q1: It seems that the proposed Relax-and-Merge framework is designed specifically for the Euclidean space. However, many fair algorithms can also be used to solve the case when data points are in a general metric space. Can the proposed method achieve better performances in general metric spaces compared with other fair clustering algorithms?"

Thanks for this question. Although the focus of our paper is mainly about k-means in Euclidean space, it is also deserved to provide the discussion for possible extensions.

Our framework can be extended to a general metric space. We have added the proofs and discussions in Appendix F.6 of our revised paper. The proof idea is similar with Lemma 1. However, in a general metric space, we cannot use Proposition 1. Hence, we have to use the basic triangle inequality instead, which weakens the approximation ratio of our framework to ($1+2\rho)$ for fair $k$-median and $(2+8\rho)$ for fair $k$-means.

Unfortunately, we should admit that the theoretical guarantees of our framework in general metric space are weaker than (Bera et al.). The primary reason is that in general metric space we do not have a proper candidate set similar to approximate centroid set in Euclidean space which holds Proposition 1. How to obtain a better candidate set is not only a potential future work of our framework but also an interesting open theoretical problem. If such a centroid set (or some similar structure) is available, we can immediately improve the approximation factor for those cases. A highlight of our current paper is that it brings a new perspective to fair clustering problems, which comes from this classical geometric structure. We hope that our work could inspire more improvements to fair clustering in future.

"Q2: Since the $\epsilon$-approximation centroid set construction method does not rely on a specific constraint during the clustering process, whether the proposed framework can be extended to solve other fair clustering problems using $\epsilon$-approximation centroid set construction method?"

The answer is yes! Thank you for this question. The critical requirements of using our framework are twofold: (1) mergeable clusters; (2) optimal locating on centroids. (1) means that if you merge more than one feasible cluster into one, the merged cluster still remains feasible. (2) requires each optimal center to be the centroid of its clients.

There are other types of constrained $k$-means satisfying (1) and (2), such as anonymous $k$-means [1, 3], which requires the number of points in every cluster to exceed some given threshold; and diversity $k$-means [2], which ensures the fraction of same-colored points in each cluster does not below some given parameter.

In addition, we need to design a specific assignment algorithm for each constrained $k$-means. For the aformentioned two constrained problems, we can find assignment algorithms in [3].

[1] Ahmadian S, Swamy C. Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers[C]//43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2016.

[2] Li J, Yi K, Zhang Q. Clustering with diversity[C]//Automata, Languages and Programming: 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I 37. Springer Berlin Heidelberg, 2010: 188-200.

[3] Ding H, Xu J. A unified framework for clustering constrained data without locality property[J]. Algorithmica, 2020, 82(4): 808-852.

"Q3: In the experimental parts, the authors only compare the clustering quality of the proposed algorithms with other fair clustering algorithms. Can the authors give a detailed comparison between the running time of the proposed framework and other existing fair clustering algorithms?"

Thank you for this question. For the comparison of running time, please refer to our global response. We have also added Appendix F.6 to further discuss this issue.

"Q4: The clustering quality of the proposed algorithm rely heavily on the weighted algorithm used to reduce the number of partitions. However, in the experimental parts, there is no detailed description of which weighted algorithm is chosen and how the weighted algorithm is executed. Which weighted k-means algorithm is used in the experiments for Algorithm 1? Did the authors choose a PTAS for the experiments?"

We used $k$-means++ in our experimental section, as it is one of the most popular $k$-means algorithms in practice. In previous works, such as Bera et al., they also used $k$-means++ to solve the vanilla $k$-means problem. We have added a sentence in our experimental part to clarify this in our revised version. We did not choose PTAS for $k$-means as our $k$-means solver because it is too slow and complicated to implement. We used $k$-means++ as the $k$-means solver for our algorithm and all baselines.

"Q1: Is it possible to obtain fair k - clustering without any fairness violation without the requirement of equally sized groups?"

Thank you for your thoughtful question. We can consider the following two cases separately (the latter one is more complicated than the first one):

For the disjoint setting (where each point can belong to only one group), our new method declines the worst-case violation factor to 2. If we want to eliminate the violation completely, as far as we know, previous work has achieved this by either (1) compromising the approximation ratio, such as [1] and [2], where they obtained an $O(\log k)$-approximation for fair $k$-median without violations, or (2) employing methods that are not strictly within polynomial time, such as the quasi-polynomial-time approximation scheme by [2], which also avoids violations. Achieving a (polynomial-time) constant-factor approximation without violations for $k$-clustering remains an open problem. We also add these references to our revised paper.

For the overlapping setting (where a point can belong to multiple groups), to the best of our knowledge, no existing assignment algorithm completely avoids violations. Due to the hardness of the integer programming involved, eliminating the violations tends to introduce certain side effects, such as a larger approximation ratio or non-polynomial time complexity. We think this is an important open problem in the area of fair clustering, which is deserved to study in future.

We will add more discussions and references in our paper about this topic after collecting all the final comments from the reviewers and ACs after this rebuttal phase.

[1] Dai Z, Makarychev Y, Vakilian A. Fair representation clustering with several protected classes[C]//Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency. 2022: 814-823.

[2] Wu D, Feng Q, Wang J. Approximation algorithms for fair k-median problem without fairness violation[J]. Theoretical Computer Science, 2024, 985: 114332.

"Q2: Can the method be extended to other clustering costs like k-median? It appears that proofs rely heavily on the cost being squared Euclidean distance."

Thanks for this question. Although the focus of our paper is mainly about k-means in Euclidean space, it is also deserved to provide the discussion for possible extensions. We need to discuss this issue separately for different scenarios.

If we consider the $k$-median problem in Euclidean space, where facilities can lie in the ambient space, an immediate question is how to obtain a candidate set. In $k$-means, we have the method of [Matousek (2000)] to provide an "approximate centroid set". However, for $k$-median, as far as we know there is currently no method to construct such a candidate set to cover all potential optimal facilities. We would like to list it as an important open problem deserved to study in future.

If we consider the $k$-median problem in general metric space or in Euclidean space but with a potential facility set whose size is polynomial and given, our framework can be extended to address this issue. We just directly use the whole facility set as our candidate set. As for the analysis, although we cannot use Proposition 1 to handle the $k$-median problem, we can use the triangle inequality instead. By doing so, we get a weaker upper bound of the approximation ratio compared with our result for Euclidean k-means -- $(1+2\rho)$ for the $k$-median problem, where $\rho$ is the approximation ratio for vanilla $k$-median. If the doubling dimension of metric space is fixed (this is a common assumption for some applications, since the doubling dimension measures data’s intrinsic dimension, which is usually low), then equipped with PTAS for vanilla $k$-median (such as the methods from [1,2]), we can obtain a $3+\epsilon$-approximation for fair $k$-median. The detailed proof is provided in Appendix E of our revised paper.

Finally, we would like to emphasize that the major bottleneck of our approach for handling k-median and non-Euclidean space is the lack of the centroid set for them. If such a centroid set (or some similar structure) is available, we can immediately improve the approximation factor for those cases. A highlight of our current paper is that it brings a new perspective to fair clustering problems, which comes from this classical geometric structure. We hope that our work could inspire more improvements to fair clustering in future.

[1] Friggstad Z, Rezapour M, Salavatipour M R. Local search yields a PTAS for k-means in doubling metrics[J]. SIAM Journal on Computing, 2019, 48(2): 452-480.

[2] Cohen-Addad V, Feldmann A E, Saulpic D. Near-linear time approximation schemes for clustering in doubling metrics[J]. Journal of the ACM (JACM), 2021, 68(6): 1-34.

"Q3: Can you clarify how the solution to the k-sparse Wasserstein barycenter solution is guaranteed to be a distribution? Is the optimization slightly changed?"

After we run Algorithm 1, we obtain the support $S$ (the locations of centers) of the returned solution and the assignment matrix $\phi_S^*$. The key question is how to ensure that the summation of the weight of points in $S$ is equal to 1. The solution is simple: we just consider an arbitrary given distribution (or "group" in the context of fair $k$-means), e.g., $P^{(l)}$. For every facility $f$ in $S$, we define its weight $w(f) = \sum_{p\in P^{(l)}} \phi^*_S (p, f)$. This ensures that the total weight of $S$ must be equal to the total weight of $P^{(l)}$, which is 1 because $P^{(l)}$ is a distribution. The choice of $P^{(l)}$ can be arbitrary because, recall that $k$-sparse WB can be seen as a special fractional version of strictly fair $k$-means, meaning no matter which given distribution you choose, you will obtain the same weight distribution of $S$. The optimization will not change by setting the weight of $S$ because the weight of $S$ does not affect the cost.

Thans for this question, and we also add the explaination to our revised paper Appendix D.

"Weakness 1: There is time complexity analysis of algorithm 1. However, there can be a comparison with the Bera et al. and Bohm et al. papers to get an idea of the tradeoff between approximation factor and time complexity. Empirical results should also result the time parameter. There are some experiments in the appendix, but they are just for your algorithm. Same goes for the violation ratio."

Thanks for your helpful suggestions.

• For the comparison of running time, please refer to our global response. We have also added Appendix F.6 to further discuss this issue.

• Regarding the violation factor, we have proven a 2-violation factor in theory, outperforming the baseline NIPS19 under the disjoint group setting (it is 7-violation for general overlapping setting, but in their paper they also claimed an improvement to 3-violation for disjoint setting). However, in practice, we find that NIPS19 (Bera et al.) always achieves near 0-violation factor, while ours tends to remain a small violation (as shown in Appendix F.7). The primary reason is that our rounding technique models the rounding procedure as an optimization (min-cost flow), that is, as long as the violation is within the bound 2, the algorithm will always search for the solution who has the cost as low as possible (i.e., reducing the cost has a higher priority than reducing the violation). This results in a tendency that, even when our method has achieved a low-violation-factor solution at some point, it will continue searching for a lower-cost solution albeit suffering a larger violation (as long as it is bounded by 2). This tendency often leads our method to find lower-cost solutions but with slightly higer violation in practice, compared with the rounding method of NIPS19.

  There are two simple ways to reduce the violation of our method in practice. The first solution is to add an early-stop rule to our rounding method that stops when all entries in the assignment matrix are integral. By doing so, we found that our rounding algorithm can also achieve near 0-violation in our datasets. The second solution is to run both rounding algorithms of NIPS19 and ours, then choose the solution that you prefer (note that the rounding step is very fast and takes only a minor part of the whole time, usually less than 1%, so running two rounding algorithms does not affect the total runtime too much). The rounding method of NIPS19 will stop immediately when all entries in the assignment matrix are integral, but it also gives up the potential to explore new solutions with lower costs. But our algorithm can address this shortcoming. Therefore, we can choose the one based on our priority, either focusing more on the cost or the violation.

"Weakness 2: In terms of presentation, I think, it would be better to move some experiments to the main paper and one more proof to the appendices."

Thank you for your suggestion. We will carefully modify our paper’s structure after collecting all the final comments from the reviewers and ACs after this rebuttal phase.