A 9/7 -Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs

摘要

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 improve