CS Paper Radar

Local Search for Fair Max-Min Diversification

Sepideh Mahabadi, Shyam Narayanan, Varun Sivashankar

cs.DS cs.CG ·submitted 2026-09-29 02:07 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Rounding the Ball LP for Fair Max-Min Diversification

cs.DS ·2026-09-28 ·Julián Mestre, Lam Khai Trinh, Anthony Wirth
theory similarity 0.74
Abstract · 15 pages, 1 figure

Given $n$ points in a metric space, partitioned into groups, $X_1,\dots,X_m$, and integer quotas, $k_1,\dots,k_m$, summing to $k$, the Fair Max-Min Diversification problem asks for a set of $k$ points, exactly $k_i$ from each group $X_i$, maximizing the minimum pairwise distance. Addanki et al. (ICDT 2022) described a ball LP for this problem and rounding algorithms that yield a factor 2 approximation whose fairness holds only in expectation and a factor 6 approximation with relaxed fairness guarantees, as well as an $(m+1)$-approximation with exact fairness. We introduce two new algorithms. The first method refines the rounding of Addanki et al., yielding a 2-approximate solution that is $\varepsilon$-fair with high probability, meaning that from every group $X_i$, at least $(1-\varepsilon) k_i$ points are chosen. The second method in polynomial time returns a 4-approximation to the optimal value of the exact fairness version. In time $n^{O(1)} 2^{O(k)}$, which is fixed-parameter tractable in $k$, we achieve an exactly fair 4-approximation. Our method adapts the augmenting procedure behind Haxell's theorem (Graphs Combin., 1995). This approximation factor does not depend on $m$. Moreover, we show that no rounding of the ball LP achieves a smaller factor with exact fairness.

0.19

Fair Diversity Maximization via Local Search

cs.DS cs.CG ·2026-10-03 ·Mohammad Ansari, Sina Azizeddin, AmirMohammad Bandari, Pouria Mahmoudkhan, Hamid Zarabi-Zadeh
similarity 0.73
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.

0.08

Subexponential Parameterized Approximation for Group-Fair Euclidean $k$-Center

cs.DS ·2026-10-14 ·Rudranarayan Kar, Diya Roy, Abhishek Sahu
similarity 0.67
Abstract

Clustering is a basic tool for grouping data into meaningful classes, but in many applications the resulting clusters must also respect the fairness conditions among different groups. We study this direction for the group-fair Euclidean $k$-center problem in fixed dimension, where the input points are partitioned into disjoint color classes, and every cluster must satisfy given lower and upper bounds on the fraction of each color. We give a separator-based recursive approximation algorithm for the continuous-center setting. The main idea is to first reduce the continuous search space to a finite candidate center set and then use the geometric sphere separators to break the instance into smaller subproblems. Our algorithm gives a bicriteria approximation: the clustering radius is within a factor of $(1+ε)$ of the optimum exactly fair solution, while the fairness bounds are relaxed only by a multiplicative factor. For fixed dimension, number of colors, and approximation parameters, the running time is polynomial in input size and subexponential in $k$. A recent IJCAI-ECAI2026 result gives a $(1+ε)$-approximation for group-fair $k$-center in bounded doubling metrics with running time $(k/ε)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. In the fixed-dimensional Euclidean setting considered here, we improve the dependence on $k$ to subexponential, while allowing continuous centers. The fairness guarantees of the two results are different: the previous work allows an additive fairness violation, whereas our algorithm uses a controlled multiplicative relaxation.

0.07

On Diverse Solutions to Max-k-CSP and Bounded Degree k-SAT

cs.DS ·2026-09-27 ·Mayank Goswami, Adarsh Srinivasan
similarity 0.65
Abstract

We study the problem of generating diverse solutions to Max-$k$-CSP and bounded-degree $k$-SAT, focusing on two distinct metrics: constraint diversity and variable diversity. For constraint diversity, the goal is to output $s \geq 2$ assignments to the CSP such that each assignment satisfies a $c$-fraction of the constraints, while maximizing the diversity among the $0$-$1$ indicator vectors of satisfied constraints in the Hamming metric. By reducing this to a multi-criteria optimization problem, we design $poly(n,s)$ time approximation algorithms that return s assignments achieving provable bi-criteria guarantees on both the fraction of satisfied constraints and diversity of the constraint vectors. For variable diversity, the objective is to maximize the Hamming distance between the assignments, while also maximizing the number of constraints satisfied. For Max-$k$-CSP instances when the desired number of solutions is $s=2^{O(n)}$, we implicitly represent these diverse approximate solutions by constructing linear codes within the solution space. Finally, we investigate variable diversity for $k$-SAT in the Lovász Local Lemma regime. In this setting, we establish NP-hardness for the exact diversity problem (computing the diameter of the solution space) and provide a polynomial-time approximation algorithm to efficiently generate diverse satisfying assignments.

0.35

Dimension Reduction and Coresets for Min-Sum $k$-Clustering

cs.DS cs.CG ·2026-10-28 ·Asaf Dallal, Robert Krauthgamer
similarity 0.63
Abstract

The min-sum $k$-clustering problem asks to partition an input of $n$ points into $k$ clusters so as to minimize the total pairwise distance within clusters. It is a natural alternative to center-based objectives when the data is not well captured by a small set of representative points. We study for this problem two standard sketching methods, dimension reduction and coresets, which represent the input more compactly while preserving the min-sum cost of every $k$-partition up to $1\pm\varepsilon$ factor. Our first contribution addresses dimension reduction in Euclidean space. The Johnson-Lindenstrauss (JL) Lemma readily implies that a random linear map to target dimension $t=O(\varepsilon^{-2}\log n)$ preserves, with high probability, the min-sum cost of all $k$-partitions. We show that target dimension $t=O(\varepsilon^{-2}(ddim\cdot\log(1/\varepsilon)+\log k+\log\log n))$ suffices for Euclidean inputs of doubling dimension at most $ddim$, and moreover this bound is nearly optimal. We also show that target dimension $t=O(\varepsilon^{-2}(\log(1/\varepsilon)+\log k+\logΔ))$ suffices for Euclidean inputs of aspect ratio at most $Δ$. Our second contribution is to design the first $\varepsilon$-coreset for metric min-sum $k$-clustering. It is actually a movement-based coreset, has size $(1/\varepsilon)^{O(ddim)} k\log n$ for inputs of doubling dimension at most $ddim$, and can be constructed in randomized near-linear-time. We further use these coresets to design streaming algorithms for the problem.

0.18

Streaming algorithms for robust max-min diversification

cs.LG ·2026-10-01 ·Andrea Pietracaprina, Geppino Pucci, Stefano Zanon
similarity 0.62
Abstract

Given a set of $n$ points $X$ in a metric space and an integer $k$, max-min diversification aims to select $k$ points of $X$ maximizing their minimum pairwise distance. This objective function is however highly vulnerable to noisy points. In[Amagata, AAAI23], a robust formulation is proposed which addresses this vulnerability by excluding solutions containing any of $z$ outliers, defined as the $z$ points in $X$ with the largest nearest-neighbor distances. That paper also presents a coreset-based streaming algorithm for the new formulation, based on a suitable inlier-outlier separation assumption. However, we identify three shortcomings in the algorithm by [Amagata, AAAI23]: its coreset construction requires an offline computation over $X$, which needs memory linear in $n$, in stark contrast with the typical goals of stream processing; the one-pass procedure used to extract the solution from the coreset may return fewer than $k$ points (hence, an unfeasible solution) because it permanently discards points too far from the current solution; and its outlier-exclusion guarantee is only probabilistic and weakens as the coreset size shrinks. In contrast, we present a deterministic coreset-based algorithm that, under a natural inlier-outlier separation assumption (similar to the one used in [Amagata, AAAI23]), returns exactly $k$ inliers which are a $(2+\varepsilon)$-approximate solution, for any $\varepsilon>0$, thus only $\varepsilon$ above the best polynomial-time sequential approximation, even without outliers. Its one-pass streaming implementation adapts obliviously to the dataset's doubling dimension $D$ and, for wide ranges of $k$, $z$, $\varepsilon$, and $D$, it uses memory independent of $n$. For sufficiently long streams, its amortized update time is proportional to the coreset size, thus also independent of $n$.

0.28

Socially Fair Clustering: Parameterized Approximation and Local Search

cs.DS ·2026-08-30 ·Aditya Anand, Yury Makarychev, Liren Shan
hot direction similarity 0.61
Abstract · 31 pages, APPROX 2026

We study the Socially Fair Clustering problem introduced by Abbasi, Bhaskara, and Venkatasubramanian (2021) and Ghadiri, Samadi, and Vempala (2021), along with its extension, the $(p,q)$-Socially Fair Clustering problem. This problem generalizes $k$-medians and $k$-means to settings where data points are partitioned into $\ell$ groups, and the goal is to find a fair clustering that is simultaneously good for all groups. We present several algorithms for this problem. For $\ell_p$-Socially Fair Clustering, we give the first constant-factor FPT-approximation parameterized by the number of groups $\ell$, resolving the open question raised by Ghadiri, Singh, and Vempala (2022). Our main ingredient is a new algorithm for closing additional centers in parameterized time inspired by local search. We then turn to the more general $(p,q)$-Socially Fair Clustering problem. The known algorithm for this problem, proposed by Chlamtáč, Makarychev, and Vakilian (2022) achieves a very good approximation but is complex, slow and difficult to implement. We analyze the performance of a simple local search algorithm and show that it provides an $O(q)$ approximation in the worst case. Finally, we design approximation algorithms for the facility location variant of the problem, where the number of facilities (centers) is not fixed in advance, and opening each facility incurs an opening cost. Unlike in previous work, we do not assume these opening costs are the same for all groups.

0.58

Maximum Matching-Match: Hardness and Approximation

cs.DS cs.CC ·2026-09-07 ·Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
similarity 0.61
Abstract

In this paper, we study \textsc{MaxMMP}, an optimization variant of the Matching-Match Puzzle introduced by Iburi and Uehara (FUN 2024). Given a graph, a partial vertex coloring, and a multiset of colored sticks, the goal is to complete the coloring and assign the sticks to graph edges so as to maximize the number of satisfied edges. We first prove that \textsc{MaxMMP} is APX-hard by an reduction from \textsc{Max-Cut}. The hardness already holds with two colors, no precolored vertices, and only bichromatic sticks. We then give a simple deterministic $\frac{2}{c(c+1)}$-approximation for completely uncolored instances, improving to $\frac{2}{c(c-1)}$ when all sticks are bichromatic. Next, we obtain a randomized $\frac{1-\frac{1}{e}}{2c}$-approximation for arbitrary instances with $c$ colors by reducing the remaining coloring choices to monotone submodular maximization under a partition matroid. On bipartite graphs, the approximation ratio improves to $\frac{1-\frac{1}{e}}{c}$. For every fixed $c$, we further obtain deterministic $\frac{1}{2c}$ and $\frac{1}{c}$-approximations on general and bipartite graphs, respectively, in time $n^{O(c^2)}$. Finally, for every fixed number of colors, we show that \textsc{MaxMMP} can be solved exactly in time $n^{O(c^2)}$ on trees and on cographs.

0.49