Back to Search
Start Over
BEATING THE INTEGRALITY RATIO FOR s-t-TOURS IN GRAPHS.
- Source :
-
SIAM Journal on Computing . 2023, Vol. 52 Issue 6, p1-48. 48p. - Publication Year :
- 2023
-
Abstract
- Among various variants of the traveling salesman problem (TSP), the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3 2, and an approximation algorithm matching this ratio. In this paper, we go below this threshold: we devise a polynomialtime algorithm for the s-t-path graph TSP with approximation ratio 1.497. Our algorithm can be viewed as a refinement of the 3 2 -approximation algorithm in [A. SebH o and J. Vygen, Combinatorica, 34 (2014), pp. 597--629], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics). [ABSTRACT FROM AUTHOR]
- Subjects :
- *TRAVELING salesman problem
*APPROXIMATION algorithms
*GRAPH algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 52
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 175713352
- Full Text :
- https://doi.org/10.1137/18M1227135