2026-07-25T15:31:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15881 2024-03-06T10:56:25Z ddc:004 open_access

Improved Approximation and Scalability for Fair Max-Min Diversification Addanki, Raghavendra McGregor, Andrew Meliou, Alexandra Moumoulidou, Zafeiria algorithmic fairness diversity maximization data selection approximation algorithms Given an n-point metric space ({𝒳},d) where each point belongs to one of m = O(1) different categories or groups and a set of integers k₁, …, k_m, the fair Max-Min diversification problem is to select k_i points belonging to category i ∈ [m], such that the minimum pairwise distance between selected points is maximized. The problem was introduced by Moumoulidou et al. [ICDT 2021] and is motivated by the need to down-sample large data sets in various applications so that the derived sample achieves a balance over diversity, i.e., the minimum distance between a pair of selected points, and fairness, i.e., ensuring enough points of each category are included. We prove the following results: 1) We first consider general metric spaces. We present a randomized polynomial time algorithm that returns a factor 2-approximation to the diversity but only satisfies the fairness constraints in expectation. Building upon this result, we present a 6-approximation that is guaranteed to satisfy the fairness constraints up to a factor 1-ε for any constant ε. We also present a linear time algorithm returning an m+1 approximation with exact fairness. The best previous result was a 3m-1 approximation. 2) We then focus on Euclidean metrics. We first show that the problem can be solved exactly in one dimension. {For constant dimensions, categories and any constant ε > 0, we present a 1+ε approximation algorithm that runs in O(nk) + 2^{O(k)} time where k = k₁+…+k_m.} We can improve the running time to O(nk)+poly(k) at the expense of only picking (1-ε) k_i points from category i ∈ [m]. Finally, we present algorithms suitable to processing massive data sets including single-pass data stream algorithms and composable coresets for the distributed processing. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Raghavendra Addanki and Andrew McGregor and Alexandra Meliou and Zafeiria Moumoulidou 2022 Is Part Of LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2022.7 urn:nbn:de:0030-drops-158812 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.7 eng https://creativecommons.org/licenses/by/4.0/legalcode