Papers for

data summarization engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

New approach improves fair diversity selection with fixed group quotas

Fair Diversity Maximization via Local Search

Abstract: Diversity maximization is a fundamental optimization problem with applications in machine learning, data summarization, information retrieval, and recommendation systems. In many such applications, the data are partitioned into groups, and the selected subset must satisfy prescribed group quotas. We study Fair Diversity Maximization: given a set of points in a metric space partitioned into $m$ groups, the goal is to select exactly $k_i$ points from each group $i$ while maximizing the minimum pairwise distance among the selected points. The best previously known approximation guarantee is $m+1$, which grows linearly with the number of groups. We show that this dependence on $m$ is not fundamental. We present a new local-search framework that yields a $4$-approximation for any constant number of groups, with no restrictions on the metric space or on the size of the selected set. To the best of our knowledge, this is the first constant-factor approximation whose guarantee is independent of the number of groups in this general setting. Our framework maintains all group quotas exactly while progressively eliminating violations of the diversity objective. We further develop a specialized algorithm for two groups that achieves a $2$-approximation, improving the previous best factor of $3$. This factor is optimal: unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm can achieve an approximation factor strictly better than $2$, even for the unconstrained case.

Sat 3 OctData Structures and AlgorithmsComputational Geometry
The gist
Selecting diverse groups of items is important for recommendations and summaries, but it's tricky when you need a specific number from each category. The authors improved previous methods by creating an algorithm that picks groups to maximize diversity while exactly meeting group size requirements, and it works well even as the number of groups grows. They also made a special version for two groups that is as good as possible with today's computer limits. This means better balanced and varied selections can be made more efficiently.
Open → 2610.04404v1