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
Publication:484552
DOI10.1007/S00493-014-2960-3zbMATH Open1340.90201arXiv1201.1870OpenAlexW1999799345MaRDI QIDQ484552FDOQ484552
Publication date: 7 January 2015
Published in: Combinatorica (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1201.1870
Recommendations
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)
Cites Work
- Matching theory
- The traveling salesman problem on a graph and some related integer polyhedra
- Matching, Euler tours and the Chinese postman
- Connections in combinatorial optimization
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Title not available (Why is that?)
- Title not available (Why is that?)
- A THEOREM ON INDEPENDENCE RELATIONS
- Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph
- Biconnectivity approximations and graph carvings
- The Traveling Salesman Problem with Distances One and Two
- A Randomized Rounding Approach to the Traveling Salesman Problem
- An improved upper bound for the TSP in cubic 3-edge-connected graphs
- Approximating Graphic TSP by Matchings
- Minimum-weight two-connected spanning networks
- Title not available (Why is that?)
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Heuristic analysis, linear programming and branch and bound
- In Pursuit of the Traveling Salesman
- A construction for binary matroids
- 2-Matchings and 2-covers of hypergraphs
- Conservative weightings and ear-decompositions of graphs
- \(\frac {13}{9}\)-approximation for graphic TSP
- TSP on Cubic and Subcubic Graphs
- Non-Separable and Planar Graphs
- Eight-Fifth Approximation for the Path TSP
- Improving christofides' algorithm for the s-t path TSP
- A generalization of Kónig's theorem
Cited In (72)
- Reducing Path TSP to TSP
- A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs
- Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies
- On the Metric $s$--$t$ Path Traveling Salesman Problem
- An improved upper bound for the universal TSP on the grid
- Travelling on graphs with small highway dimension
- Sublinear algorithms for \((1.5+\epsilon)\)-approximate matching
- Constant Factor Approximation for ATSP with Two Edge Weights
- Polyhedral techniques in combinatorial optimization: matchings and tours
- Approximation algorithms for flexible graph connectivity
- Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
- 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
- Tour recommendation for groups
- Flexible graph connectivity
- Title not available (Why is that?)
- A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
- Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
- A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
- Traveling salesman problems in temporal graphs
- On the Metric $s$--$t$ Path Traveling Salesman Problem
- An LP-based approximation algorithm for the generalized traveling salesman path problem
- Simple cubic graphs with no short traveling salesman tour
- An Improved Approximation Algorithm for the Matching Augmentation Problem
- Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
- 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
- Approximation hardness of graphic TSP on cubic graphs
- Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
- Better approximability results for min-max tree/cycle/path cover problems
- The Steiner traveling salesman problem with online edge blockages
- A LP-based approximation algorithm for generalized traveling salesperson path problem
- Weighted amplifiers and inapproximability results for travelling salesman problem
- Beating the Integrality Ratio for $s$-$t$-Tours in Graphs
- Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP
- On the integrality ratio of the subtour LP for Euclidean TSP
- 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
- The temporal explorer who returns to the base
- An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
- Better \(s-t\)-tours by Gao trees
- Constant factor approximation for ATSP with two edge weights
- Improved approximations for cubic bipartite and cubic TSP
- Flexible Graph Connectivity
- Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
- New inapproximability bounds for TSP
- A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem
- 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
- New Approximation Algorithms for (1,2)-TSP
- TSP Tours in Cubic Graphs: Beyond 4/3
- 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
- The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem
- An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem
- Improved Approximations for Cubic Bipartite and Cubic TSP
- An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
- LP-relaxations for tree augmentation
- Improving on best-of-many-Christofides for \(T\)-tours
- Approximation algorithms with constant ratio for general cluster routing problems
- Reassembling trees for the traveling salesman
- Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges
- Better s-t-Tours by Gao Trees
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)
