Improved Approximations for Cubic Bipartite and Cubic TSP

We show improved approximation guarantees for the traveling salesman problem on cubic bipartite graphs and cubic graphs. For cubic bipartite graphs with n nodes, we improve on recent results of Karp and Ravii¾ź[10] by giving a "local improvement" algorithm that finds a tour of length at most $$5/4n-2$$. For 2-connected cubic graphs, we show that the techniques of Momke and Svenssoni¾ź[11] can be combined with the techniques of Correa et al.i¾ź[6], to obtain a tour of length at most $$4/3-1/8754n$$.