Improved algorithms find fair diverse sets with guaranteed distances
Rounding the Ball LP for Fair Max-Min Diversification
Data Structures and Algorithms
Summary
The problem is about picking points from different groups so that the chosen points are not too close to each other, while respecting how many points must come from each group. Previous methods could either keep exact group counts but had poorer distance guarantees or keep distances good only on average. This paper offers new ways to pick points that get close to the best minimum distance while almost exactly meeting group quotas with high probability. When the exact group counts are required, their algorithm still improves the distance guarantee compared to before. They also show no method using the existing linear program can do better with exact fairness.
What this means in practice
- •For data scientists: Select diverse and representative data points from multiple categories while almost exactly meeting category size requirements to improve fairness in training datasets.
- •For resource allocation planners: Assign resources fairly to predefined groups maximizing minimum diversity distance with guaranteed approximation and exact group quotas.
Authors
Julián Mestre, Lam Khai Trinh, Anthony Wirth
Abstract
Given $n$ points in a metric space, partitioned into groups, $X_1,\dots,X_m$, and integer quotas, $k_1,\dots,k_m$, summing to $k$, the Fair Max-Min Diversification problem asks for a set of $k$ points, exactly $k_i$ from each group $X_i$, maximizing the minimum pairwise distance. Addanki et al. (ICDT 2022) described a ball LP for this problem and rounding algorithms that yield a factor 2 approximation whose fairness holds only in expectation and a factor 6 approximation with relaxed fairness guarantees, as well as an $(m+1)$-approximation with exact fairness. We introduce two new algorithms. The first method refines the rounding of Addanki et al., yielding a 2-approximate solution that is $\varepsilon$-fair with high probability, meaning that from every group $X_i$, at least $(1-\varepsilon) k_i$ points are chosen. The second method in polynomial time returns a 4-approximation to the optimal value of the exact fairness version. In time $n^{O(1)} 2^{O(k)}$, which is fixed-parameter tractable in $k$, we achieve an exactly fair 4-approximation. Our method adapts the augmenting procedure behind Haxell's theorem (Graphs Combin., 1995). This approximation factor does not depend on $m$. Moreover, we show that no rounding of the ball LP achieves a smaller factor with exact fairness.