A 97-approximation algorithm for graphic TSP in cubic bipartite graphs

DOI10.1016/J.DAM.2015.10.038MaRDI QIDQ298977zbMATH OpenOpenAlexFDO

Authors Jeremy A. Karp, R. Ravi

Publication date 21 June 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsBarnette's conjecturecombinatorial optimizationtraveling salesman problem

Mathematics Subject Classification ID

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

Abstract: We prove new results for approximating Graphic TSP. Specifically, we provide a polynomial-time frac{9}{7}-approximation algorithm for cubic bipartite graphs and a (frac{9}{7}+frac{1}{21(k-2)})-approximation algorithm for k-regular bipartite graphs, both of which are improved approximation factors compared to previous results. Our approach involves finding a cycle cover with relatively few cycles, which we are able to do by leveraging the fact that all cycles in bipartite graphs are of even length along with our knowledge of the structure of cubic graphs.

Recommendations

• A \(\frac {9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs
• Graphic TSP in cubic graphs
• Improved approximations for cubic bipartite and cubic TSP
• Improved Approximations for Cubic Bipartite and Cubic TSP
• TSP on cubic and subcubic graphs

Cites work

• A Randomized Rounding Approach to the Traveling Salesman Problem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs
• An improved upper bound for the TSP in cubic 3-edge-connected graphs
• Approximating Graphic TSP by Matchings
• Improved Approximations for Cubic Bipartite and Cubic TSP
• Short Tours through Large Linear Forests
• 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
• Solution of a Large-Scale Traveling-Salesman Problem
• The traveling salesman problem on cubic and subcubic graphs
• TSP tours in cubic graphs: beyond 4/3
• Worst-case comparison of valid inequalities for the TSP

Cited in

(8)

• Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs
• Improved approximations for cubic bipartite and cubic TSP
• Decomposition theorems for square-free 2-matchings in bipartite graphs
• A 4/3-approximation for TSP on cubic 3-edge-connected graphs
• A polynomial-space exact algorithm for TSP in degree-6 graphs
• A \(\frac {9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs
• Improved Approximations for Cubic Bipartite and Cubic TSP
• Approximation hardness of graphic TSP on cubic graphs

This page was built for publication: A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs

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