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
From MaRDI portal
(Redirected from Publication:484552)
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
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
Abstract: We prove new results for approximating the graphic TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees. For the graphic TSP itself, we improve the approximation ratio to 7/5. For a generalization, the connected--join problem, we obtain the first nontrivial approximation algorithm, with ratio 3/2. This contains the graphic --path-TSP as a special case. Our improved approximation guarantee for finding a smallest 2-edge-connected spanning subgraph is 4/3. The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs. The same methods also provide the lower bounds (arising from LP relaxations) that we use to deduce the approximation ratios.
Recommendations
Cites work
- scientific article; zbMATH DE number 1187146 (Why is no real title available?)
- scientific article; zbMATH DE number 3512137 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- 2-Matchings and 2-covers of hypergraphs
- A Randomized Rounding Approach to the Traveling Salesman Problem
- A THEOREM ON INDEPENDENCE RELATIONS
- A construction for binary matroids
- A generalization of Kónig's theorem
- An improved upper bound for the TSP in cubic 3-edge-connected graphs
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Approximating Graphic TSP by Matchings
- Biconnectivity approximations and graph carvings
- Connections in combinatorial optimization
- Conservative weightings and ear-decompositions of graphs
- Eight-fifth approximation for the path TSP
- Heuristic analysis, linear programming and branch and bound
- Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
- Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph
- In pursuit of the traveling salesman. Mathematics at the limits of computation
- Matching theory
- Matching, Euler tours and the Chinese postman
- Minimum-weight two-connected spanning networks
- Non-Separable and Planar Graphs
- TSP on cubic and subcubic graphs
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The Traveling Salesman Problem with Distances One and Two
- The traveling salesman problem on a graph and some related integer polyhedra
- \(\frac {13}{9}\)-approximation for graphic TSP
Cited in
(74)- An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs
- Approximating TSP walks in subcubic graphs
- Parity polytopes and binarization
- Graph-TSP from Steiner cycles
- Towards better inapproximability bounds for TSP: a challenge of global dependencies
- Tour recommendation for groups
- Flexible graph connectivity
- scientific article; zbMATH DE number 7525493 (Why is no real title available?)
- A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
- A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- Traveling salesman problems in temporal graphs
- A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
- Reducing Path TSP to TSP
- New approximation algorithms for \((1,2)\)-TSP
- Approximating minimum-cost connected \(T\)-joins
- An LP-based approximation algorithm for the generalized traveling salesman path problem
- Simple cubic graphs with no short traveling salesman tour
- A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges
- A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs
- The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem
- Two-connected spanning subgraphs with at most \(\frac{10}{7}{\mathrm{OPT}}\) edges
- An Improved Approximation Algorithm for the Matching Augmentation Problem
- Approximation hardness of graphic TSP on cubic graphs
- Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
- On the Metric $s$--$t$ Path Traveling Salesman Problem
- The Steiner traveling salesman problem with online edge blockages
- Better approximability results for min-max tree/cycle/path cover problems
- Constant factor approximation for ATSP with two edge weights (extended abstract)
- A LP-based approximation algorithm for generalized traveling salesperson path problem
- Weighted amplifiers and inapproximability results for travelling salesman problem
- On the integrality ratio of the subtour LP for Euclidean TSP
- Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP
- Beating the Integrality Ratio for $s$-$t$-Tours in Graphs
- An improved upper bound for the universal TSP on the grid
- TSP tours in cubic graphs: beyond 4/3
- Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem
- A 4/3-approximation for TSP on cubic 3-edge-connected graphs
- On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
- A deterministic better-than-3/2 approximation algorithm for metric TSP
- A simple LP-based approximation algorithm for the matching augmentation problem
- Travelling on graphs with small highway dimension
- The temporal explorer who returns to the base
- Better \(s-t\)-tours by Gao trees
- Constant factor approximation for ATSP with two edge weights
- Improved approximations for cubic bipartite and cubic TSP
- An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
- Better \(s\)-\(t\)-tours by Gao trees
- On the metric \(s\)-\(t\) path traveling salesman problem
- Improving TSP tours using dynamic programming over tree decompositions
- Flexible Graph Connectivity
- New inapproximability bounds for TSP
- Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
- A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem
- Sublinear algorithms for \((1.5+\epsilon)\)-approximate matching
- A PTAS for three-edge-connected survivable network design in planar graphs
- Shorter tours and longer detours: uniform covers and a bit beyond
- The salesman's improved tours for fundamental classes
- Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours
- \(\frac{13}{9}\)-approximation for graphic TSP
- A note on the tour problems in two-terminal series-parallel graphs
- An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
- The traveling salesman problem on cubic and subcubic graphs
- Approximating minimum-cost connected \(T\)-joins
- An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
- Improved Approximations for Cubic Bipartite and Cubic TSP
- LP-relaxations for tree augmentation
- Improving on best-of-many-Christofides for \(T\)-tours
- Approximation algorithms with constant ratio for general cluster routing problems
- Overview of new approaches for approximating TSP
- Reassembling trees for the traveling salesman
- Polyhedral techniques in combinatorial optimization: matchings and tours
- Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
- Eight-fifth approximation for the path TSP
This page was built for publication: 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q484552)
