Beating the Integrality Ratio for s-t-Tours in Graphs

DOI10.1137/18M1227135zbMATH Open1528.90231OpenAlexW3007218717MaRDI QIDQ6139824FDOQ6139824

Authors Vera Traub, Jens Vygen 

Publication date 19 December 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.03112

zbMATH Keywords

approximation algorithmtraveling salesman problemear decompositionintegrality ratio

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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).

Recommendations

• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• Approaching \(\frac 23\) for the \(s\)-\(t\)-path TSP
• Approaching 3/2 for the \(s\)-\(t\)-path TSP
• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem

Cites work

• scientific article; zbMATH DE number 3313442 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A 1.5-approximation for path TSP
• A Multiple Exchange Property for Bases
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• An exchange theorem for bases of matroids
• An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approaching 3/2 for the \(s\)-\(t\)-path TSP
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• Approximation hardness of graphic TSP on cubic graphs
• Better \(s-t\)-tours by Gao trees
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Connections in combinatorial optimization
• Conservative weightings and ear-decompositions of graphs
• Eight-fifth approximation for the path TSP
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph
• Removing and adding edges for the traveling salesman problem
• 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
• Some properties of basic families of subsets
• The salesman's improved paths through forests
• Two-connected spanning subgraphs with at most \(\frac{10}{7}{\mathrm{OPT}}\) edges
• \(\frac{13}{9}\)-approximation for graphic TSP

Cited in

(1)

• Better \(s-t\)-tours by Gao trees

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)