Talk by Tony Wirth (University of Sydney) on Fair Max-Min Diversification

On September 30, 2026, 11:00-12:00, we are happy to host a talk by Tony Wirth on fair max-min diversification. The talk will take place in Erzherzog-Johann-Platz 1, 1040 Wien, in Seminarraum FB 02 10 (second floor). You are most welcome to join us.

Title: Rounding the Ball LP for Fair Max-Min Diversification

Speaker: Tony Wirth, University of Sydney

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 \emph{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.

About: Tony Wirth is Professor and Head in the School of Computer Science at The University of Sydney. Prior to this, he had a 19-year career in the School of Computing and Information Systems at Melbourne, also his undergraduate institution. His PhD was at Princeton, advised by Moses Charikar. Tony’s interests are several, and include: approximation algorithms for graph problems, specifically correlation clustering; streaming problems, specifically max coverage and set cover; search with errors; and compression and search in text archives and streams.