Rounding the Ball LP for Fair Max-Min Diversification

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 $\epsilon$-fair with high probability, meaning that from every group $X_i$, at least $(1-\epsilon )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.

15 pages, 1 figure