Beating the Integrality Ratio for s-t-Tours in Graphs
From MaRDI portal
Publication:6139824
DOI10.1137/18M1227135zbMATH Open1528.90231arXiv1804.03112OpenAlexW3007218717MaRDI QIDQ6139824FDOQ6139824
Authors: Vera Traub, Jens Vygen 
Publication date: 19 December 2023
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Abstract: Among various variants of the traveling salesman problem, 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 polynomial-time 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 by SebH{o} and Vygen [2014], 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).
Full work available at URL: https://arxiv.org/abs/1804.03112
Cites Work
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Connections in combinatorial optimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph
- Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Approximation Algorithms for Orienteering and Discounted-Reward TSP
- Some properties of basic families of subsets
- A Multiple Exchange Property for Bases
- Conservative weightings and ear-decompositions of graphs
- Eight-fifth approximation for the path TSP
- Approximation hardness of graphic TSP on cubic graphs
- An exchange theorem for bases of matroids
- Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges
- Better \(s-t\)-tours by Gao trees
- \(\frac{13}{9}\)-approximation for graphic TSP
- An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
- Improving Christofides' Algorithm for the s-t Path TSP
- Removing and Adding Edges for the Traveling Salesman Problem
- A 1.5-Approximation for Path TSP
- The Salesman’s Improved Paths through Forests
- Approaching 3/2 for the s - t -path TSP
- A constant-factor approximation algorithm for the asymmetric traveling salesman problem
- An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP
Cited In (1)
This page was built for publication: Beating the Integrality Ratio for $s$-$t$-Tours in Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139824)
