- 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
-
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 . 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.
-
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
-
An inconsistent definition in the central approximation proof. Definition 6 subtracts , whereas the subsequent arguments require . 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.
-
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
-
Clarification of the repair vector definition. Should the indicator in Definition 6 depend on rather than ? 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?
-
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 repair iterations per guess.
-
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 , , and , particularly the exponent’s dependence on , 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
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.
We thank the reviewer for the positive feedback. We address their questions below.
We thank the reviewer for pointing this out. Definition 6 contains a typo. The insertion term should be c(p) instead of 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.
We revised Algorithm 1 to clarify this trimming step. After each repair, we trim each group to exactly ki 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 k repair iterations per guess.
The outer binary search handles unsuccessful guesses. It checks whether the returned set S satisfies the exact quotas and the required separation conditions. If S is valid, the search records it and tries larger guesses. If S is invalid, initialization fails the within-group separation check, or
FindRepairreturnsNoneat any point, the search tries smaller guesses.Our analysis guarantees a valid solution for every μ≤OPT. Thus the search records a valid solution at OPT or at a larger guess, which suffices for the claimed approximation guarantee.
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)logn) for the 4-approximation and O(n2klogn) for the 2-approximation algorithm.