Faster Algorithms for Fair Max-Min Diversification in $\mathbbR^d$
<|reference_start|>Faster Algorithms for Fair Max-Min Diversification in $\mathbbR^d$: The task of extracting a diverse subset from a dataset, often referred to as maximum diversification, plays a pivotal role in various real-world applications that have far-reaching consequences. In this work, we delve into the realm of fairness-aware data subset selection, specifically focusing on the problem of selecting a diverse set of size $k$ from a large collection of $n$ data points (FairDiv).   The FairDiv problem is well-studied in the data management and theory community. In this work, we develop the first constant approximation algorithm for FairDiv that runs in near-linear time using only linear space. In contrast, all previously known constant approximation algorithms run in super-linear time (with respect to $n$ or $k$) and use super-linear space. Our approach achieves this efficiency by employing a novel combination of the Multiplicative Weight Update method and advanced geometric data structures to implicitly and approximately solve a linear program. Furthermore, we improve the efficiency of our techniques by constructing a coreset. Using our coreset, we also propose the first efficient streaming algorithm for the FairDiv problem whose efficiency does not depend on the distribution of data points. Empirical evaluation on million-sized datasets demonstrates that our algorithm achieves the best diversity within a minute. All prior techniques are either highly inefficient or do not generate a good solution.<|reference_end|>
@article{kurkure2024faster,
    title={Faster Algorithms for Fair Max-Min Diversification in $\mathbb{R}^d$},
    author={Yash Kurkure, Miles Shamo, Joseph Wiseman, Sainyam Galhotra, Stavros
  Sintos},
    journal={SIGMOD 2024},
    year={2024},
    doi={10.1145/3654940},
    archivePrefix={arXiv},
    eprint={2404.04713},
    primaryClass={cs.DB cs.DS}
}