Approximating Graphic TSP by Matchings
From MaRDI portal
Publication:5494987
DOI10.1109/FOCS.2011.56zbMath1292.68169MaRDI QIDQ5494987
Publication date: 30 July 2014
Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)
Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (31)
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 ⋮ 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 ⋮ An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph ⋮ An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem ⋮ Cubic TSP: A 1.3-Approximation ⋮ Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies ⋮ A 4/3-approximation for TSP on cubic 3-edge-connected graphs ⋮ A deterministic better-than-3/2 approximation algorithm for metric TSP ⋮ Spanning closed walks and TSP in 3-connected planar graphs ⋮ 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 ⋮ 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 ⋮ New inapproximability bounds for TSP ⋮ Special Frequency Quadrilaterals and an Application ⋮ Simple cubic graphs with no short traveling salesman tour ⋮ Improved integrality gap upper bounds for traveling salesperson problems with distances one and two ⋮ \(\frac{13}{9}\)-approximation for graphic TSP ⋮ TSP Tours in Cubic Graphs: Beyond 4/3 ⋮ Reassembling Trees for the Traveling Salesman ⋮ Constant factor approximation for ATSP with two edge weights ⋮ Unnamed Item ⋮ On the minimum leaf number of cubic graphs ⋮ Unnamed Item ⋮ Approximating TSP walks in subcubic graphs ⋮ Approximating minimum-cost connected \(T\)-joins ⋮ An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
This page was built for publication: Approximating Graphic TSP by Matchings
