Metraipolis › archive › dc_2ab40771e471

Constant-Factor Approximations for the Biased Traveling Salesman Problem and Its Path Variant — arXiv:2611.07348

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.07348
License (as archived)
CC0-1.0
Archived
2026-11-06T14:54:21.130Z
SHA-256 of the archived text
0a9e12cc31dd918179f7590a8ec2b8fd0a094de4c44353fa863762b7f356dad9
Stable URL of this page
https://metraipolis.com/documento/dc_2ab40771e471

How to cite

Constant-Factor Approximations for the Biased Traveling Salesman Problem and Its Path Variant — arXiv:2611.07348 — arXiv (en), https://arxiv.org/abs/2611.07348 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2ab40771e471 (Metraipolis archive dc_2ab40771e471, sha256 0a9e12cc31dd918179f7590a8ec2b8fd0a094de4c44353fa863762b7f356dad9)
BibTeX
@misc{dc2ab40771e471,
  title = {Constant-Factor Approximations for the Biased Traveling Salesman Problem and Its Path Variant — arXiv:2611.07348},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.07348},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2ab40771e471; sha256 0a9e12cc31dd918179f7590a8ec2b8fd0a094de4c44353fa863762b7f356dad9},
  year = {2026}
}

Archived text

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

The metric traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization that asks for a minimum-cost Hamiltonian cycle in a complete undirected graph with $N$ vertices, where edge costs satisfy the triangle inequality. The biased TSP (BTSP) is a natural generalization of the metric TSP, in which the vertex set is partitioned into $k$ subsets: edge costs satisfy the triangle inequality within each subset, while edges crossing the subsets may violate the triangle inequality by a certain bias factor. This model captures scenarios in which distances are metric only locally but may be distorted across different regions or types of vertices. In this paper, we study approximation algorithms for the BTSP and its path variant, the biased traveling salesman path problem (BTSPP), which asks for a minimum-cost Hamiltonian path. Previously, constant-factor approximation algorithms were known only for the case $k=2$. Whether the BTSP and the BTSPP admit constant-factor approximation algorithms for any fixed integer $k>2$ has remained an open question. We resolve this question affirmatively. We show that both the BTSP and the BTSPP admit $O(k)$-approximation algorithms with running time $N^{O(2^k k!)}$. Moreover, for the BTSPP with $k=2$, we propose an improved $(\alpha+2+\varepsilon)$-approximation algorithm, where $\alpha<3/2-10^{-34}$ is the best-known approximation ratio for the metric TSP, improving upon the previous ratio of $4$

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.07348 — 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-11-06T14:26:57.628Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).