2026-08-15T12:59:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4703 2024-03-06T10:35:16Z ddc:004 open_access

A 9/7 -Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs Karp, Jeremy A. Ravi, R. Approximation algorithms traveling salesman problem Barnette’s conjecture combinatorial optimization We prove new results for approximating Graphic TSP. Specifically, we provide a polynomial-time 9/7-approximation algorithm for cubic bipartite graphs and a (9/7+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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeremy A. Karp and R. Ravi 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.284 urn:nbn:de:0030-drops-47034 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.284 eng https://creativecommons.org/licenses/by/3.0/legalcode