Diversity Maximization: Algorithms for Distant $k$-Subsets

Diversity maximization is a fundamental problem in combinatorial optimization with applications in fairness-aware machine learning, clustering, and data summarization, and has attracted significant attention in theoretical computer science. We study the Distant $k$-Subsets Problem (DKSP): given a metric space $(X,d)$ with $|X|=n$ and an integer $k$, find two disjoint subsets $S,T\subseteq X$, each of size $k$, maximizing ${\min }_{s\in S,t\in T}d(s,t)$. This problem arises as a key subroutine in composable coresets for diversity maximization, and improvements can yield better approximations for related objectives such as remote-matching and pseudoforest. It also appears in practice: a variation was featured in the ICPC World Finals 2024. Mahabadi and Narayanan gave a $(4/ϵ)$-approximation for this subproblem when $n\ge 2k^{1+ϵ}+k$. For any $ϵ>0$, we present a deterministic combinatorial algorithm achieving a $\left(1+\lceil 1/ϵ\rceil \right)$-approximation under the same condition. In particular, for $ϵ=1$, this yields a $2$-approximation when $n\ge 2k^2+k$; the factor $2$ is optimal for general metrics unless $P=NP$. More generally, any polynomial-time $(2-\eta )$-approximation for constant $\eta >0$ would imply an algorithm for the $k$-Biclique problem, even though DKSP is polynomial-time solvable when $n=2k$. For $d$-dimensional Euclidean metrics, we obtain improved guarantees: a $(2+\sqrt{2})$-approximation when $n\ge 3\cdot 2^{d-1}k$, and a $(2+\sqrt{d}/c)$-approximation when $n\ge (2d+c^d)k$. In particular, for $d=2$ and $c=1$, this gives a $(2+\sqrt{2})$-approximation when $n\ge 5k$, yielding near-$2$ guarantees under linear constraints on $n$ for constant $d$.