Local search improves fair max min diversity selection
Local Search for Fair Max-Min Diversification
Data Structures and AlgorithmsComputational Geometry
Summary
Choosing a diverse group of points usually means picking items that are far apart from each other. When these points are divided into categories (colors) and you need to pick a certain number from each category, the problem becomes harder. The authors introduce a method using local search that can find a good mix exactly meeting these category counts while keeping the points well spaced out. Their method works efficiently even when points can belong to multiple categories, and they improve upon earlier approaches that either took much longer, gave weaker solutions, or only approximated category requirements.
What this means in practice
- •For data scientists: Select representative, well-separated samples from multiple categories exactly meeting category counts.
- •For marketing analysts: Create diverse customer groups meeting strict segment sizes for targeted campaigns.
Authors
Sepideh Mahabadi, Shyam Narayanan, Varun Sivashankar
Abstract
Given $n$ points in a metric space, Max-Min diversification asks for a subset of $k$ points maximizing the minimum pairwise distance between the selected points. This is arguably the most fundamental notion of diversity with applications across a wide range of domains. We consider this problem under partition constraints, previously studied as Fair Max-Min Diversification (FMMD). Here, each point has a color in $[m]$, and a feasible solution must contain exactly $k_i$ points of color $i$, where $k_1,\ldots,k_m$ are prescribed parameters satisfying $\sum_i k_i=k$. We give the first constant factor approximation for the problem using local search, that runs in time $f(m)\cdot \operatorname{poly}(n)$, in which all constraints are satisfied exactly. All previously known algorithms either provided an $\widetilde Θ(m)$ approximation factor, had running times exponential in the solution size $k$, or satisfied the fairness constraints only approximately or in expectation. We further generalize our result to the problem where each point may belong to an arbitrary subset of colors. Given lower and upper bounds $\ell_i$ and $u_i$ for every color $i$, the goal is to find $k$ points whose color counts satisfy all these bounds while maximizing their diversity.