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

DOI10.1016/J.DAM.2015.10.038zbMATH Open1339.05389arXiv1311.3640OpenAlexW2964056290MaRDI QIDQ298977FDOQ298977

Authors: Jeremy A. Karp, R. Ravi 

Publication date: 21 June 2016

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

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.

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

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

zbMATH Keywords

combinatorial optimizationapproximation algorithmstraveling salesman problemBarnette's conjecture

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Decomposition theorems for square-free 2-matchings in bipartite graphs
• Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs
• Approximation hardness of graphic TSP on cubic graphs
• A 4/3-approximation for TSP on cubic 3-edge-connected graphs
• Improved approximations for cubic bipartite and cubic TSP
• Improved Approximations for Cubic Bipartite and Cubic TSP

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)