CS Paper Radar

Rounding the Ball LP for Fair Max-Min Diversification

Julián Mestre, Lam Khai Trinh, Anthony Wirth

cs.DS ·submitted 2026-09-28 04:19 UTC · v1
theory

Abstract

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.

Comment
15 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

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.74
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

Local Search for Fair Max-Min Diversification

cs.DS cs.CG ·2026-09-29 ·Sepideh Mahabadi, Shyam Narayanan, Varun Sivashankar
similarity 0.74
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.

0.15

A $(3+ε)$-Approximation for Fair $k$-Means and a Matching Lower Bound

cs.CG cs.LG ·2026-09-07 ·Kangke Cheng, Guanlin Mo, Shihong Song, Hu Ding
theory similarity 0.72
Abstract

Fair clustering aims to prevent algorithmic bias against protected groups. We study Euclidean fair $k$-means, in which the proportion of each protected group in every cluster lies between prescribed lower and upper bounds. Because these constraints violate the nearest-center assignment property, center selection is coupled with point assignment. We introduce the drift-regularized relaxation, a new convex relaxation solved by a modified Frank-Wolfe method with linear-programming iterations, whose optimality condition controls the cost of converting its solution into $k$ fair clusters. Combined with any $ρ$-approximation algorithm for weighted $k$-means, the relaxation yields an exactly fair fractional solution of cost at most $2ρ+1+ε$ times the fractional optimum, improving the previous ratio $1+4ρ+ε$. In fixed dimension, this improves the best known ratio from $5+O(ε)$ to $3+O(ε)$. The fractional solution can be rounded to an integral one without changing the centers or increasing the cost, at a bounded additive violation of the fairness bounds. We also show that a $(3-δ)$-approximation is NP-hard for every fixed $δ>0$, even on the line with fractional assignments, so $3$ is the exact approximation threshold for fractional fair $k$-means in fixed dimension. The same guarantees hold for $k$-sparse Wasserstein barycenters, a special case of fractional fair $k$-means. More generally, they hold whenever every cluster must satisfy given homogeneous linear inequalities in the fractions of its points, such as a bound on the ratio between two groups or on the average of a numerical attribute in every cluster.

0.09

Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering

cs.LG cs.AI ·2026-09-06 ·Zeyu Lin, Chaoqi Jia, Longkun Guo, Chao Chen
top venue similarity 0.70
Abstract

Motivated by the growing importance of fairness in machine learning, fair $k$-center clustering has attracted considerable research attention as a fundamental problem. In this problem, a dataset is partitioned into $m$ disjoint groups, and the objective is to select $k$ data points as centers, subject to upper bounds on the number of centers chosen from each group, aiming to minimize the maximum distance between any data point and its assigned center. Focusing on Euclidean spaces, which are ubiquitous in machine learning applications, we first develop a parameterized approximation algorithm for Euclidean fair $k$-center with an approximation ratio of $2.732$. By incorporating this algorithm as a post-processing stage into a one-pass streaming framework for large-scale data, we obtain an approximation ratio of $4.464$. These ratios can be further respectively improved to $2.414$ and $3.828$ with a runtime exponential on $k$. To ensure polynomial-time complexity, we further design a one-pass streaming algorithm with an approximation ratio of $4.732$, which can be further improved to $4.42$, outperforming the state-of-the-art ratio. Finally, extensive experiments show that our methods significantly outperform state-of-the-art approaches in terms of clustering accuracy.

0.40

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

cs.DS ·2026-10-14 ·Rudranarayan Kar, Diya Roy, Abhishek Sahu
similarity 0.68
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

Socially Fair Clustering: Parameterized Approximation and Local Search

cs.DS ·2026-08-30 ·Aditya Anand, Yury Makarychev, Liren Shan
hot direction similarity 0.66
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

Optimally Selecting Representative Agents from a Metric Space

cs.GT cs.LG ·2026-08-29 ·Benjamin Cookson, Eva Deltl, Yeeseok Oh
theory similarity 0.65
Abstract

This paper studies the problem of proportionally fair clustering, where the goal is to select $k$ ``centers'' from a metric space that fairly represent a set of agents who also lie in the metric space. Specifically, we focus on finding a clustering satisfying a fairness property known as the Droop core. In the practical special case in which the set of feasible center locations contains every agent location, the previous best-known result guaranteed a $(1 + \sqrt{2})$-approximation of the Droop core, while the best-known lower bound was $2$. In this paper, we show that this lower bound is tight and that a clustering in the $2$-Droop core always exists. Further, we show that such a clustering can be achieved by only selecting centers from locations in the metric space where an agent resides. We establish this using Scarf's theorem guaranteeing a nonempty core for balanced non-transferable utility games. This result has several interesting corollaries. Most notably, it resolves the $β$-plurality problem of Aronov et al. [2021] for general metric spaces. The main result of this paper was generated by $\mathtt{ChatGPT}$-$\mathtt{5.6}$-$\mathtt{Sol}$ through a series of interactions with the authors. The authors of this paper verified the generated proof and rewrote it for clarity.

0.27

Target-Stratified Fair Range Summaries: Improved Fair $\varepsilon$-Nets and Geometric Hitting Sets

cs.DS cs.DM ·2026-09-17 ·Mingchao Zhou, Lei Zhao, Zhipeng Cai, Zhao Zhang
theory similarity 0.64
Abstract

Compact summaries are a key tool for approximate query processing over large datasets. For range-query workloads, an $\varepsilon$-net provides a small summary that hits every sufficiently large range. However, classical $\varepsilon$-nets only guarantee range validity and do not control the group composition of the selected tuples. As a result, the summary may be range-valid but poorly representative, which can propagate imbalance to downstream query results. Motivated by recent work on fair $\varepsilon$-nets and fair geometric hitting sets \cite{dehghankar2025fair}, we study fairness-aware range summaries under prescribed target group ratios. Different from previous sample-and-repair approach, we propose a target-stratified sampling method. For demographic parity (in which the ratio of fairness is determined by group proportion), our sample size is $O(A_{\varepsilon})$, coinciding with the standard $\varepsilon$-net bound, improving previous bound of $O\!\left(A_\varepsilon\log\frac{k}{\varphi}\right)$. For custom-ratio targets (in which the ratio of fairness is determined by manually defined proportion), our sample size is $O(A_Γ)$, where $Γ$ is a parameter measuring the gap between the customized ratio and the demographic parity; we prove that this dependence on $Γ$ is unavoidable, with a worst-case lower bound of $Ω(Γ/\varepsilon)$. Using our target-stratified sampling method, we could improve the previous approximation ratio for the fair geometric hitting set problem by a logarithmic factor, and making use of this result, we could in turn improve the size of custom-ratio fair $\varepsilon$-net. Experiments on real and synthetic datasets demonstrate that our method constructs smaller fair summaries than existing approaches, scales to large datasets and fine-grained group constraints, and improves downstream range query processing.

0.19