Metraipolis › archive › dc_d45faa50d097
Approximation Algorithms for Perfect Fair-Triangle Packing — arXiv:2608.07674
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.07674
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T09:16:35.833Z
- SHA-256 of the archived text
f45b633aff96e63b0732696dba5344f8d0c6e4429a6b0738b7333dd3f6272da5- Stable URL of this page
https://metraipolis.com/documento/dc_d45faa50d097
How to cite
Approximation Algorithms for Perfect Fair-Triangle Packing — arXiv:2608.07674 — arXiv (en), https://arxiv.org/abs/2608.07674 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d45faa50d097 (Metraipolis archive dc_d45faa50d097, sha256 f45b633aff96e63b0732696dba5344f8d0c6e4429a6b0738b7333dd3f6272da5)
BibTeX
@misc{dcd45faa50d097,
title = {Approximation Algorithms for Perfect Fair-Triangle Packing — arXiv:2608.07674},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.07674},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d45faa50d097; sha256 f45b633aff96e63b0732696dba5344f8d0c6e4429a6b0738b7333dd3f6272da5},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.07674. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In this paper, we study the {\em perfect fair-triangle packing} problem (abbreviated as PFTP), which incorporates the fairness criterion from {\em fair clustering} into the {\em maximum-weight triangle packing} problem. Specifically, the input is an edge-weighted complete graph $G = (V, E)$ with $|V| = 3n$, where each vertex is colored red or blue. A {\em fair triangle} is a triangle containing vertices of both colors. PFTP asks for a partition of $V$ into $n$ fair triangles such that the total edge weight is maximized. To the best of our knowledge, this is the first paper to study PFTP. PFTP is NP-hard. Our main contributions are a deterministic $\frac 13$-approximation algorithm running in $O(n^3)$ time and an improved randomized $(\frac {16}{47}-\epsilon)$-approximation algorithm running in $O(n^4)$ time, where $\epsilon > 0$ is a fixed small constant. The deterministic algorithm is matching-based whereas the randomized algorithm employs several additional techniques, including maximum-weight $[1, 2]$-factor, a random cycle-breaking procedure, and maximum-weight matchings. Keywords: Triangle packing; fairness; approximation algorithms; randomized algorithms
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.07674 — 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-19T09:13:57.829Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).