An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs

DOI10.1137/19M1259353zbMath1441.90139OpenAlexW3013264052MaRDI QIDQ5220466

Alantha Newman

Publication date: 26 March 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/19m1259353

zbMATH Keywords

traveling salesman problemcirculationsLP rounding

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• 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
• Matchings in regular graphs
• Worst-case analysis of a new heuristic for the travelling salesman problem
• \(\frac{13}{9}\)-approximation for graphic TSP
• The traveling salesman problem on cubic and subcubic graphs
• An improved upper bound for the TSP in cubic 3-edge-connected graphs
• Removing and Adding Edges for the Traveling Salesman Problem
• The traveling salesman problem on a graph and some related integer polyhedra
• A Randomized Rounding Approach to the Traveling Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees

This page was built for publication: An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs