text: 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.
  @cite_5: We consider most of the known classes of valid inequalities for the graphical travelling salesman polyhedron and compute the worst-case improvement resulting from their addition to the subtour polyhedron. For example, we show that the comb inequalities cannot improve the subtour bound by a factor greater than 10 9. The corresponding factor for the class of clique tree inequalities is 8 7, while it is 4 3 for the path configuration inequalities.
  @cite_1: The RAND Corporation in the early 1950s contained “what may have been the most remarkable group of mathematicians working on optimization ever assembled” [6]: Arrow, Bellman, Dantzig, Flood, Ford, Fulkerson, Gale, Johnson, Nash, Orchard-Hays, Robinson, Shapley, Simon, Wagner, and other household names. Groups like this need their challenges. One of them appears to have been the traveling salesman problem (TSP) and particularly its instance of finding a shortest route through Washington, DC, and the 48 states [4, 7].
summary: One value related to the ability to approximate TSP is the integrality gap, which is the worst-case ratio between the optimal solution for a TSP instance and the solution to a linear programming relaxation called the subtour relaxation @cite_1 . A long-standing conjecture (see, e.g., @cite_5 ) for Metric TSP is that the integrality gap is @math . One source of motivation for studying Graphic TSP is that the family of graphs with two vertices connected by three paths of length @math has an integrality gap that approaches @math . This family of graphs demonstrates that Graphic TSP captures much of the complexity of the more general Metric TSP problem.