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 Ravi 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 Svensson can be combined with the techniques of Correa, Larre and Soto, to obtain a tour of length at most (4/3− 1/8754)n.