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 $m$ groups, the goal is to select exactly $k_i$ points from each group $i$ while maximizing the minimum pairwise distance among the selected points. The best previously known approximation guarantee is $m+1$, which grows linearly with the number of groups. We show that this dependence on $m$ is not fundamental. We present a new local-search framework that yields a $4$-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 $2$-approximation, improving the previous best factor of $3$. This factor is optimal: unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm can achieve an approximation factor strictly better than $2$, even for the unconstrained case.