Beating the Integrality Ratio for $s$-$t$-Tours in Graphs
From MaRDI portal
Publication:6139824
DOI10.1137/18m1227135zbMath1528.90231arXiv1804.03112OpenAlexW3007218717MaRDI QIDQ6139824
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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Better \(s-t\)-tours by Gao trees
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- \(\frac{13}{9}\)-approximation for graphic TSP
- Some properties of basic families of subsets
- An exchange theorem for bases of matroids
- An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP
- Conservative weightings and ear-decompositions of graphs
- An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
- Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph
- Improving Christofides' Algorithm for the s-t Path TSP
- Removing and Adding Edges for the Traveling Salesman Problem
- Approximation hardness of graphic TSP on cubic graphs
- Eight-Fifth Approximation for the Path TSP
- The Salesman’s Improved Paths through Forests
- A constant-factor approximation algorithm for the asymmetric traveling salesman problem
- A 1.5-Approximation for Path TSP
- Approaching 3/2 for the s - t -path TSP
- Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges
- Approximation Algorithms for Orienteering and Discounted-Reward TSP
- A Multiple Exchange Property for Bases
