Metraipolis › archive › dc_c3d9ea044f36
Approximating the Rural Postman Problem below 3/2 — arXiv:2608.27607
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.27607
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T11:52:23.083Z
- SHA-256 of the archived text
87c063bdc1d300178660d3080829aff570f3bacd69f465aefd4c926bbbae1cec- Stable URL of this page
https://metraipolis.com/documento/dc_c3d9ea044f36
How to cite
Approximating the Rural Postman Problem below 3/2 — arXiv:2608.27607 — arXiv (en), https://arxiv.org/abs/2608.27607 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c3d9ea044f36 (Metraipolis archive dc_c3d9ea044f36, sha256 87c063bdc1d300178660d3080829aff570f3bacd69f465aefd4c926bbbae1cec)
BibTeX
@misc{dcc3d9ea044f36,
title = {Approximating the Rural Postman Problem below 3/2 — arXiv:2608.27607},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.27607},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c3d9ea044f36; sha256 87c063bdc1d300178660d3080829aff570f3bacd69f465aefd4c926bbbae1cec},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.27607. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We give an approximation algorithm for the rural postman problem with approximation ratio strictly smaller than $3/2$. We obtain this result by adapting to the rural postman problem the technique of sampling from maximum entropy distributions for the metric traveling salesman problem of Karlin, Klein, and Oveis Gharan. We also observe that, for every fixed $\varepsilon>0$, any $\alpha$-approximation algorithm for the metric traveling salesman problem yields an $(\alpha+\varepsilon)$-approximation algorithm for the rural postman problem; this implication is already implicit in the treatment of edges that must be traversed in the work of Lampis on the inapproximability of the traveling salesman problem. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-31 in cs.DS). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2608.27607 — 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-17T11:23:11.250Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-31?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).