Fair Diversity Maximization with Few Representatives Conference: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 3–7, 2025; Toronto, ON, Canada Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’25), August

Florian Adriaens, Nikolaj Tatti · 2025

Read Fair Diversity Maximization with Few Representatives Conference: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 3–7, 2025; Toronto, ON, Canada Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’25), August by Florian Adriaens, Nikolaj Tatti (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-08110.txt.

Introduction

Picking a varied shortlist from a huge pool is a classic computing problem, and fairness adds a twist: each group in the pool must get its share of seats. Florian Adriaens and Nikolaj Tatti study the version where only a few picks per group are wanted. Their method works in stages, first pruning points that sit too close to same-group neighbors, then sorting points into clusters at random, and finally choosing one fitting pick from each cluster.

The random method beats the best known guarantee for how close the result comes to the ideal spread. Tests on large real datasets back up the math. The work suits tasks like fair shortlists, sample panels, and search results that must span groups without losing variety.

Catalog record

CREATORFlorian Adriaens, Nikolaj Tatti
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-08110

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fair Diversity Maximization with Few Representatives Conference: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 3–7, 2025; Toronto, ON, Canada Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’25), August 3–7, 2025, Toronto, ON, Canada DOI: 10.1145/3711896.3736950 ISBN: 979-8-4007-1454-2/2025/08 CCS: Theory of computation Design and analysis of algorithms Florian Adriaens, Nikolaj Tatti Abstract . Diversity maximization problem is a well-studied problem where the goal is to find k k diverse items. Fair diversity maximization aims to select a diverse subset of k k items from a large dataset, while requiring that each group of items be well represented in the output. More formally, given a set of items with labels, our goal is to find k k items that maximize the minimum pairwise distance in the set, while maintaining that each label is represented within some budget. In many cases, one is only interested in selecting a handful (say a constant) number of items from each group. In such scenario we show that a randomized algorithm based on padded decompositions improves the state-of-the-art approximation ratio to log ⁡ ( m ) / ( 3 ​ m ) \sqrt{\log(m)}/(3m) , where m m is the number of labels. The algorithms work in several stages: ( i i ) a preprocessing pruning which ensures that points with the same label are far away from each other, ( i ​ i ii ) a decomposition phase, where points are randomly placed in clusters such that there is a feasible solution with maximum one point per cluster and that any feasible solution will be diverse, ( i ​ i ​ i ) (iii) assignment phase, where clusters are assigned to labels, and a representative point with the corresponding label is selected from each cluster. We experimentally verify the effectiveness of our algorithm on large datasets. † † cc-license: by KDD Availability Link: The source code of this paper has been made publicly available at https://doi.org/10.5281/zenodo.15533799 . 1. Introduction Diversity maximization is an extremely well-studied task with applications in data summarization ( Celis et al. 2018 ; Chandra and Halldórsson 2001 ; Zheng et al. 2017 ) , feature selection ( Zadeh et al. 2017 ) , facility location ( Kuby 1987 ; Erkut 1990 ; Tamir 1991 ; Ravi et al. 1994 ) , recommendation systems ( Abbassi et al. 2013 ; Kaminskas and Bridge 2016 ; Castells et al. 2021 ) , web search ( Xin et al. 2006 ; Radlinski and Dumais 2006 ; Qin et al. 2012 ; Bhattacharya et al. 2011 ) , information exposure in social networks ( Matakos et al. 2020 ) and e-commerce ( Zheng et al. 2017 ) , among others. The goal is to find a set of diverse items within the data, which means that the selected items should be highly dissimilar to each other. Diablo Canyon Seabrook South Texas Point Beach Turkey Point Columbia Shearon Harris Wolf Creek Browns Ferry Palo Verde Perry Monticello Waterford Limerick Edwin I. Hatch Clinton ANO Ginna Callaway Donald C. Cook Figure 1. Selected k=20 of existing nuclear power plants in US, at most one per state. In metric spaces this naturally translates to seeking a set with large distances between its elements. Of particular interest is the widely studied max-min diversification (MMD) objective function (also known as remote-edge or p -dispersion ), which asks for a set S of size k that maximizes the smallest pairwise distance between distinct items in S ( Erkut 1990 ; Wang and Kuo 1988 ) . This problem is \mathbf{NP} -complete, but admits a greedy 1/2 approximation in metric spaces ( Tamir 1991 ; Ravi et al. 1994 ) . Recent work has introduced group fairness constraints to the MMD problem ( Moumoulidou et al. 2020 ; Addanki et al. 2022 ; Wang et al. 2022 ; Wang et al. 2023a ; Wang et al. 2023b ; Kurkure et al. 2024 ) . One important motivation is that in some data subset selection tasks, directly combining numerical and categorical attributes into a single objective function can be troublesome (although methods exist), as it might require ad hoc decisions for discretizing numerical attributes or other pre-processing ( Moumoulidou et al. 2020 ) . Instead, formulating fairness as a constraint allows to achieve a specified level of representation of certain groups that are defined through categorical attributes, while diversity aims at achieving a high distance between numerical feature vectors. The assumption is that the universe of items V=V_{1}\cup\ldots\cup V_{m} is partitioned into m disjoint groups (also called colors or labels ). A fair solution is a set S\subseteq V of fixed size k , while requiring that S contains an appropriate amount of items from each color. Specifically, Wang et al. 2023b introduced the fair max-min diversification ( FMMD ) problem. This problem models fairness by requiring \ell_{i}\leq|S\cap V_{i}|\leq u_{i} for each i\in[m] , where \ell_{i} and u_{i} are specified parameters. These constraints capture and generalize various existing notions of group fairness such as proportional representation ( Celis et al. 2018 ; El Halabi et al. 2020 ) and equal representation ( Kleindessner et al. 2019 ) . Aside from diversity maximization, these constraints have been used in various other settings like ranking ( Celis et al. 2017 ) , clustering ( Kleindessner et al. 2019 ) , multiwinner voting ( Celis et al. 2018 ) and submodular maximization ( El Halabi et al. 2020 ) . The FMMD problem is formally described as: Problem 1 (Fair Max-Min Diversification ( FMMD ) ( Wang et al. 2023b ) ). Assume a metric space (V,d) with distance function d:V\times V\to\mathbb{R}_{\geq 0} , a partition V=V_{1}\cup\ldots\cup V_{m} into m colors, and parameters k , \ell_{i} and u_{i} for each i\in[m] . Select a set S\subseteq V of fixed size |S|=k , such that for all i\in[m]:\ell_{i}\leq|S\cap V_{i}|\leq u_{i} , while maximizing (1) \displaystyle\mathit{div}\mathopen{}\left(S\right)=\min\limits_{\begin{subarray}{c}u,v\in S\\ u\neq v\end{subarray}}d(u,v). Here, \mathit{div}\mathopen{}\left(S\right) denotes the diversity score of the set S . FMMD with Few Representatives. This paper studies FMMD in case one is interested in only a few representatives per color. There are plenty of applications where this assumption is well-motivated. Indeed, consider the case where one requires at most one representative from each color. Such fairness has been considered in prior work ( Abbassi et al. 2013 ; Haxell 2011 ; Loh and Sudakov 2007 ) . Specifically, the seminal paper of Abbassi et al. 2013 considers document presentation in the context of product search or news aggregator websites. They formulated a problem where no more than one document from the same category (e.g., from the same news channel or product brand) may appear in the output. Note that also the classic MMD problem (without fairness) is a special case of FMMD with k\leq m , by assigning each point v\in V with a unique color. A second example is following facility location problem. Suppose the U.S. government has decided to reduce its current nuclear power plants to k plants. They have a set of current locations from which they wish to select k suitable options. Each state has agreed to the placement of

Read the complete text