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/\epsilon)$-approximation for this subproblem when $n \ge 2k^{1+\epsilon}+k$. For any $\epsilon>0$, we present a deterministic combinatorial algorithm achieving a $\left(1+\left\lceil 1/\epsilon\right\rceil\right)$-approximation under the same condition. In particular, for $\epsilon=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$.