An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs

DOI10.1007/978-3-662-44777-2_61zbMATH Open1425.68475arXiv1407.2524OpenAlexW2963220947MaRDI QIDQ2921458FDOQ2921458

Alantha Newman

Publication date: 8 October 2014

Published in: Algorithms - ESA 2014 (Search for Journal in Brave)

Abstract: M"omke and Svensson presented a beautiful new approach for the traveling salesman problem on a graph metric (graph-TSP), which yields a $4/3$-approximation guarantee on subcubic graphs as well as a substantial improvement over the $3/2$-approximation guarantee of Christofides' algorithm on general graphs. The crux of their approach is to compute an upper bound on the minimum cost of a circulation in a particular network, $C(G,T)$, where $G$ is the input graph and $T$ is a carefully chosen spanning tree. The cost of this circulation is directly related to the number of edges in a tour output by their algorithm. Mucha subsequently improved the analysis of the circulation cost, proving that M"omke and Svensson's algorithm for graph-TSP has an approximation ratio of at most $13/9$ on general graphs. This analysis of the circulation is local, and vertices with degree four and five can contribute the most to its cost. Thus, hypothetically, there could exist a subquartic graph (a graph with degree at most four at each vertex) for which Mucha's analysis of the M"omke-Svensson algorithm is tight. We show that this is not the case and that M"omke and Svensson's algorithm for graph-TSP has an approximation guarantee of at most $25/18$ on subquartic graphs. To prove this, we present different methods to upper bound the minimum cost of a circulation on the network $C(G,T)$. Our approximation guarantee holds for all graphs that have an optimal solution to a standard linear programming relaxation of graph-TSP with subquartic support.

Full work available at URL: https://arxiv.org/abs/1407.2524

Recommendations

• An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs
• The traveling salesman problem on cubic and subcubic graphs
• \(\frac{13}{9}\)-approximation for graphic TSP
• \(\frac {13}{9}\)-approximation for graphic TSP
• TSP on cubic and subcubic graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (2)

• A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs
• An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs

This page was built for publication: An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921458)