A local-search framework cuts fair diversity maximization from a group-count-dependent ratio to a group-count-independent constant, with an optimal factor for two groups

For any constant number of groups, fair diversity maximization admits a polynomial-time 4-approximation whose guarantee does not grow with the number of groups. The best previously known guarantee grew linearly with the number of groups; this is the first constant-factor approximation in this general setting whose guarantee is independent of the number of groups, with no restrictions on the metric space or on the size of the selected set. Stated as Theorem 1; the proof uses repair vectors, a balance inequality, and a Steinitz-type vector-balancing argument to bound the repair-set size by a constant depending only on the number of groups, so exhaustive search finds a repair in polynomial time.

For two groups, there is a polynomial-time 2-approximation, matching the optimal approximation factor for the unconstrained problem. The previous best two-group factor was 3; this improves it to 2, and the paper notes that unless P=NP no polynomial-time algorithm can achieve a factor strictly better than 2, even for the unconstrained case. Stated as Theorem 2; the proof greedily builds a maximal auxiliary set, exploits its saturation property, and uses a counting argument over disjoint neighborhoods around optimal points to find a valid local improvement.

A unified local-repair framework improves diversity while preserving exact group quotas throughout. Unlike the earlier cluster-and-flow paradigm that enforces diversity and fairness in one shot, the framework starts from a quota-satisfying solution and replaces a bad point together with its conflict set by a repair set, strictly decreasing the number of bad points and terminating with diversity at least the target value. Framework correctness is given by the invariant argument of Theorem 3: the initial GMM step guarantees within-group separation, each repair preserves fairness and color separation, and the number of bad points is at most the selected-set size, bounding the number of iterations.

The results target max-min diversity selection with exact group quotas, apply to any metric space without restricting the selected-set size, and assume the number of groups is constant. The framework separates a generic local-repair loop from a problem-specific FindRepair subroutine, so its value lies in offering a reusable algorithmic skeleton for settings such as data summarization, retrieval, recommendation, active learning, and training-data curation where group representation must be controlled; the two-group 2-approximation applies directly when only two groups are present.

The paper presents results as theorems and proofs and reports no experimental evaluation, so practical runtime constants and behavior on large-scale data remain to be examined separately. The repair-set size bound is a function of the number of groups, so when that constant is large the practical cost of exhaustive search deserves attention. Whether the optimal two-group factor extends to any constant number of groups is explicitly left open, and the framework requires the user to design the FindRepair subroutine and choose parameters, so its transferability depends on whether that subroutine can be implemented efficiently.