Metraipolis › archive › dc_630b44d0bc86

Rounding the Ball LP for Fair Max-Min Diversification — arXiv:2609.34269

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.34269
License (as archived)
CC0-1.0
Archived
2026-10-08T00:19:01.022Z
SHA-256 of the archived text
cc683152407eda775eda67d4e19b44806c4705328befe2ed16d0462c22ef0d3d
Stable URL of this page
https://metraipolis.com/documento/dc_630b44d0bc86

How to cite

Rounding the Ball LP for Fair Max-Min Diversification — arXiv:2609.34269 — arXiv (en), https://arxiv.org/abs/2609.34269 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_630b44d0bc86 (Metraipolis archive dc_630b44d0bc86, sha256 cc683152407eda775eda67d4e19b44806c4705328befe2ed16d0462c22ef0d3d)
BibTeX
@misc{dc630b44d0bc86,
  title = {Rounding the Ball LP for Fair Max-Min Diversification — arXiv:2609.34269},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.34269},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_630b44d0bc86; sha256 cc683152407eda775eda67d4e19b44806c4705328befe2ed16d0462c22ef0d3d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.34269. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.34269 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:56:21.771Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).