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