New approach improves fair diversity selection with fixed group quotas
Fair Diversity Maximization via Local Search
Data Structures and AlgorithmsComputational Geometry
Summary
Selecting diverse groups of items is important for recommendations and summaries, but it's tricky when you need a specific number from each category. The authors improved previous methods by creating an algorithm that picks groups to maximize diversity while exactly meeting group size requirements, and it works well even as the number of groups grows. They also made a special version for two groups that is as good as possible with today's computer limits. This means better balanced and varied selections can be made more efficiently.
What this means in practice
- •For recommendation system developers: Select diverse and fair sets of recommendations that meet exact category quotas to improve user satisfaction.
- •For data summarization engineers: Create summaries from multiple data groups ensuring balanced representation and maximal diversity, useful for reports and highlights.
Authors
Mohammad Ansari, Sina Azizeddin, AmirMohammad Bandari, Pouria Mahmoudkhan, Hamid Zarabi-Zadeh
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.