acceptodds
Under review as a conference paper at ICLR 2027

Fair Diversity Maximization via Local Search

Abstract

Diversity maximization is a fundamental optimization problem with applications in machine learning, data summarization, information retrieval, and recommendation systems. In many such applications, the data are partitioned into groups, and the selected subset must satisfy prescribed group quotas. We study Fair Diversity Maximization: given a set of points in a metric space partitioned into groups, the goal is to select exactly points from each group while maximizing the minimum pairwise distance among the selected points. The best previously known approximation guarantee is , which grows linearly with the number of groups. We show that this dependence on is not fundamental. We present a new local-search framework that yields a -approximation for any constant number of groups, with no restrictions on the metric space or on the size of the selected set. To the best of our knowledge, this is the first constant-factor approximation whose guarantee is independent of the number of groups in this general setting. Our framework maintains all group quotas exactly while progressively eliminating violations of the diversity objective. We further develop a specialized algorithm for two groups that achieves a -approximation, improving the previous best factor of . This factor is optimal: unless , no polynomial-time algorithm can achieve an approximation factor strictly better than , even for the unconstrained case.

Primary area:
optimization
Keywords:
Fairness, Diversity Maximization, Approximation Algorithms, Metric Spaces

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_d7pWOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies fair diversity maximization in general metric spaces, seeking to maximize the minimum pairwise distance subject to exact group quotas. It introduces a local repair framework that progressively eliminates distance conflicts while preserving the quotas. The main contributions are a polynomial time approximation algorithm with ratio 4 for any fixed number of groups, removing the dependence of the approximation guarantee on the group count, and a specialized algorithm with the optimal ratio 2 for two groups. The analysis uses repair vectors and the Steinitz lemma for the general case, and a packing and counting argument for two groups. Validation is entirely theoretical, through correctness, termination, and approximation proofs.

Critical strengths
  1. Significant improvement in approximation guarantees. For general metric spaces under exact group quotas, the paper obtains an approximation ratio of 4 for any fixed number of groups, eliminating the linear dependence on the group count in the previous guarantee of m+1m+1. The optimal ratio of 2 for two groups further strengthens this contribution. These results constitute substantial theoretical progress in fair diversity maximization and are the primary reason supporting my recommendation for acceptance.

  2. Clear overall organization. The paper introduces a unified local repair framework before presenting the general and two-group analyses. This structure makes the main algorithmic ideas and proof strategy easy to follow, helping readers understand the relationship between the results and assess the technical contributions.

Critical weaknesses
  1. An inconsistent definition in the central approximation proof. Definition 6 subtracts 1i=c(q)\mathbf{1}_{i=c(q)}, whereas the subsequent arguments require 1i=c(p)\mathbf{1}_{i=c(p)}. In particular, the summation identity in Lemma 8 and the characterization of negative coordinates in Lemma 10 do not follow from the printed definition. This appears repairable, but the current manuscript does not present an internally consistent proof of its main general approximation guarantee. The definition and all dependent arguments should be checked and corrected.

  2. Incomplete specification of the algorithm under exact quotas. The update in Algorithm 1 can leave some groups above their quotas, but the pseudocode omits the trimming step mentioned in the proof. Consequently, the algorithm as written can return an infeasible solution. The outer threshold search also needs explicit handling of unsuccessful guesses, including cases where initialization or repair fails. These omissions are consequential because exact quota preservation is central to the contribution, and the complete algorithm cannot be implemented and verified directly from the current specification.

Questions for authors
  1. Clarification of the repair vector definition. Should the indicator in Definition 6 depend on c(p)c(p) rather than c(q)c(q)? The printed definition appears inconsistent with the summation identity in Lemma 8 and the negative coordinate argument in Lemma 10. Could you confirm the intended definition and whether this correction suffices to establish all dependent lemmas without additional changes?

  2. Clarification of the complete algorithm. Could you provide complete pseudocode specifying the quota trimming step after each repair and the handling of unsuccessful threshold guesses? In particular, how does the algorithm proceed when the initial separation requirement is not met or no repair is found? Please clarify whether the completed algorithm preserves exact quotas and terminates within at most kk repair iterations per guess.

  3. Clarification of overall running time. What are the explicit overall running times of the general algorithm and the algorithm for two groups, including threshold search and repair construction? Since the general algorithm uses exhaustive subset enumeration, it would be better to make the dependence on nn, kk, and mm, particularly the exponent’s dependence on mm, explicit.

Please feel free to correct me if I have misunderstood any part of the proof. If all of my concerns are satisfactorily addressed or shown to stem from a misunderstanding on my part, I would consider raising my score in light of the scope and quality of the work.

2 comments

We thank the reviewer for the positive feedback. We address their questions below.

Clarification of the repair vector definition. Should the indicator in Definition 6 depend on c(p)c(p) rather than c(q)c(q)? The printed definition appears inconsistent with the summation identity in Lemma 8 and the negative coordinate argument in Lemma 10. Could you confirm the intended definition and whether this correction suffices to establish all dependent lemmas without additional changes?

We thank the reviewer for pointing this out. Definition 6 contains a typo. The insertion term should be c(p)c(p) instead of c(q)c(q). Lemmas 8–10 already use the correct index, so this correction suffices for the subsequent lemmas. We fixed the definition in the revised manuscript.

Clarification of the complete algorithm. Could you provide complete pseudocode specifying the quota trimming step after each repair and the handling of unsuccessful threshold guesses? In particular, how does the algorithm proceed when the initial separation requirement is not met or no repair is found? Please clarify whether the completed algorithm preserves exact quotas and terminates within at most kk repair iterations per guess.

We revised Algorithm 1 to clarify this trimming step. After each repair, we trim each group to exactly kik_i points, by arbitrarily removing points from groups that exceed their quota. Definition 5 guarantees that each group has enough points before trimming. Clearly, deleting the extra points cannot create new close pairs. Each repair strictly decreases the number of bad points, so there are at most kk repair iterations per guess.

The outer binary search handles unsuccessful guesses. It checks whether the returned set SS satisfies the exact quotas and the required separation conditions. If SS is valid, the search records it and tries larger guesses. If SS is invalid, initialization fails the within-group separation check, or FindRepair returns None at any point, the search tries smaller guesses.

Our analysis guarantees a valid solution for every μ≤OPT\mu\le\mathrm{OPT}. Thus the search records a valid solution at OPT\mathrm{OPT} or at a larger guess, which suffices for the claimed approximation guarantee.

Clarification of overall running time. What are the explicit overall running times of the general algorithm and the algorithm for two groups, including threshold search and repair construction? Since the general algorithm uses exhaustive subset enumeration, it would be better to make the dependence on nn, kk, and mm, particularly the exponent’s dependence on mm, explicit.

We added a running-time analysis at the end of each algorithm's subsection. Including the initial sorting of the pairwise distances, the total time is O((n2+cmk2ncm)log⁡n)O((n^2+c_m k^2n^{c_m})\log n) for the 4-approximation and O(n2klog⁡n)O(n^2k\log n) for the 2-approximation algorithm.

Reviewer_d7pWOpenReview ↗

Thank you for the response.

Thank you for the thoughtful response. It addressed most of my questions. I believe this paper has good results in the group-fair diversity maximization. I would maintain my positive score and recommend for acceptance.

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

The paper studies a "group fair" version of the problem of diversity maximization under the so-called "max min" objective (minimum distance between the chosen points is maximized). In the group fair version, the input points are partitioned into mm groups, and the goal is to select exactly k_i points from group i.

The paper gives improved approximation algorithms for this problem. Previously, the best known poly time algorithms had an approximation ratio of (m+1), which grows with the number of groups. The main result of a the paper is a 4-factor approximation that runs in time O(n^{m^m}) roughly. This is polynomial in nn for all constant m. The paper also gives a "tight" 2-factor approximation for the case of 2 groups, which is also interesting (given that 2 is a classic lower bound for the max-min objective even for 1 group).

Critical strengths
  • The result is interesting from an approximation standpoint. It is obtained using a non-trivial local search procedure: the authors maintain different distance thresholds for in-group and across-group points, and they define a notion of "q-repair" that is novel; it involves swapping a constant number of points across groups (while maintaining the k_i property).

  • The definition and proof-of-existence of q-repairs is perhaps the most novel part of the paper; it uses the Steinitz lemma in a nice way to bound c_m, the number of points to consider in swaps, which is what seems to determine the running time.

Critical weaknesses
  • This is an approximation algorithms paper; while diversity maximization is of interest in ML, it is not a particularly practical algorithm and unlikely to have much effect in the practice of ML. This explains the lack of any type of experiments.
Questions for authors
  • Please write out the running time of the algorithm.
  • Are there known lower bounds against easier local search procedures? If so, citing or giving some simple examples will help gain intuition for the proposed algorithm.
2 comments

We thank the reviewer for the positive feedback. We address their questions below.

Please write out the running time of the algorithm.

We added a running-time analysis at the end of each algorithm's subsection. Including the initial sorting of the pairwise distances, the total time is O((n2+cmk2ncm)log⁡n)O((n^2+c_m k^2n^{c_m})\log n) for the 4-approximation and O(n2klog⁡n)O(n^2k\log n) for the two-group algorithm.

Are there known lower bounds against easier local search procedures? If so, citing or giving some simple examples will help gain intuition for the proposed algorithm.

A simple single-swap local search can get stuck even on the real line. Take three groups X1=0,L+1X_1 = \\{0,L+1\\}, X2=1X_2 = \\{1\\}, and X3=L,2L+1X_3 = \\{L,2L+1\\}, where k1=k2=k3=1k_1=k_2=k_3=1. Starting from S=0,1,LS=\\{0,1,L\\}, either possible single swap leaves the minimum distance at 11, while preserving group quotas. Allowing to swap multiple points in the local search, we could swap 00 and LL which would give S=L+1,1,2L+1S=\\{L+1,1,2L+1\\}, whose minimum distance is LL. Thus single-swap local optima can be arbitrarily far from global optimal. This motivates allowing more complicated swaps involving multiple points.

Reviewer_3zFHOpenReview ↗

thanks

Thanks for adding the runtime and the example. I maintain my positive score.

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

In this paper, the authors study the Fair Diversity Maximization problem, where the objective is to pick a set of points, where the points come in groups and exactly a given number must be taken from each group, so that the closest pair of chosen points is as far apart as possible. For a constant number of groups m, the best known methods were off from the best possible answer by a factor of m+1. The authors start from a valid choice and then repeatedly fix a chosen point that has another chosen point too close to it, by swapping in a small set of new points that keeps the group counts right. The authors prove that such a swap exists whenever the guessed target distance is not above the best possible value and that its size is bounded by a function of m only, using the Steinitz lemma. Checking all small swaps gives a 4-approximation for any constant m. For two groups, a simpler greedy swap gives a 2-approximation, which no fast method can beat unless P = NP. The authors give only proofs and no experiments.

Critical strengths
  1. The authors give a new proof technique that replaces the earlier cluster-and-flow method with local repair. Lemmas 7 to 11 show that a repair of size at most (2m+1)m−1(2m+1)^m-1 exists whenever the guessed target distance is at most the best possible value, by an argument about balls that do not overlap combined with the Steinitz lemma; I checked these lemmas, and they hold once the index in Definition 6 is corrected. This gives the first approximation factor that does not grow with m, for any constant m, and it is the main reason to accept.

  2. For two groups, Theorem 2 gives a 2-approximation, down from 3, which matches the known hardness bound (no better factor is possible unless P = NP). The greedy swap in Algorithm 3 and the counting proof in Lemma 14 are short and easy to verify. A tight bound for a basic problem is a clean and lasting result.

Critical weaknesses

The running time is far larger than the abstract suggests, and the gain in the factor is narrow. Algorithm 2 tries every subset of size up to (2m+1)m−1(2m+1)^m-1 (Lemma 11). The factor 4 equals the earlier m + 1 at m = 3 and beats it only for m of 4 or more, where the search is far beyond any practical size. The abstract says the dependence on m is not fundamental, but the dependence moves from the factor into the exponent of the running time, and neither Theorem 1 nor Table 1 states this cost.

Questions for authors
  1. Definition 5 allows at least kik_i points of group i, but Lemma 14 uses exactly kr−1k_r-1, and Algorithm 1 (line 6) has no step that removes extra points. Please add this step, confirm that removal cannot create new close pairs, and state what Algorithm 1 does when FindRepair returns None for a guess above the best value.

  2. What is the total running time of the method in n, k, and m, including the loop over guesses and the rounds of repair? Can a repair be found in f(m)⋅poly(n)f(m)\cdot\mathrm{poly}(n) time, for example by dynamic programming over repair vectors?

  3. Definition 6 (p. 7) counts the new point in the group of q, written c(q). The proofs of Lemmas 8 to 10 need the group of p, written c(p), since inserting p adds one point to its own group. Is this a typo?

  4. Two arXiv preprints from late September 2026 (Mahabadi et al.; Mestre et al.) report related results whose factor does not depend on m. I treat them as concurrent work and do not count them against the paper; a short comparison of factors and running times would help readers.

1 comment

We thank the reviewer for the positive feedback. We address their questions below.

  1. Definition 55 allows at least kik_i points of group i, but Lemma 14 uses exactly kr−1k_r - 1, and Algorithm 1 (line 6) has no step that removes extra points. Please add this step, confirm that removal cannot create new close pairs, and state what Algorithm 1 does when FindRepair returns None for a guess above the best value.

We added a trimming step to Algorithm 1. After each repair, it retains exactly kik_i points from each group ii. Definition 5 guarantees that each group has enough points, and deleting the extra points cannot create new close pairs.

If FindRepair returns None or initialization fails the within-group separation check, the outer binary search discards the current guess and continues with smaller values. Neither of the two situations can occur for μ≤OPT\mu\le\mathrm{OPT}.

  1. What is the total running time of the method in n, k, and m, including the loop over guesses and the rounds of repair? Can a repair be found in f(m)⋅poly(n)f(m)\cdot poly(n) time, for example by dynamic programming over repair vectors?

We added a running-time analysis at the end of each algorithm's subsection. Including the initial sorting of the pairwise distances, the total time is O((n2+cmk2ncm)log⁡n)O\left((n^2+c_m k^2n^{c_m})\log n\right) for the 4-approximation and O(n2klog⁡n)O(n^2k\log n) for the 2-approximation algorithm. The approximation factor is independent of mm, while the exponent of nn still depends on mm.

The repair-vector sum alone is insufficient as a DP state because partial repairs with the same sum can admit different insertions that preserve pairwise separation. However, the dependency-tree argument of Mahabadi et al., Lemma 3.4 can be used to sharpen the repair-size bound from (2m+1)m−1(2m+1)^m-1 to 2m−12^{m-1}, while preserving the factor-4 guarantee.

  1. Definition 6 (p. 7) counts the new point in the group of q, written c(q). The proofs of Lemmas 8 to 10 need the group of p, written c(p), since inserting p adds one point to its own group. Is this a typo?

We thank the reviewer for pointing this out. Definition 6 contains a typo. The insertion term should be c(p)c(p) instead of c(q)c(q). Lemmas 8–10 already use the correct index. We fixed the definition in the revised manuscript.

  1. Two arXiv preprints from late September 2026 (Mahabadi et al.; Mestre et al.) report related results whose factor does not depend on m. I treat them as concurrent work and do not count them against the paper; a short comparison of factors and running times would help readers.

We thank the reviewer for pointing us to these papers. We properly cited both works in our introduction. It is worth mentioining that Mestre et al.’s 4-approximation runs in 2O(k)nO(1)2^{O(k)}n^{O(1)} time, which is polynomial for k=O(log⁡n)k=O(\log n), a setting in which Moumoulidou et al. previously gave a polynomial-time 5-approximation for fixed mm.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.