Towards a 4/3 Approximation for the Traveling Salesman Problem
It has been conjectured that the integrality gap of the Held-Karp relaxation for the symmetric Traveling Salesman Problem is 4/3. We consider the special case of Graphical TSP, that is we restrict ourselves to the graph metric on an underlying unweighted graph. In an attempt to progress on the conjecture, we give an algorithm to find a closed spanning trail of length at most (4/3)n for 2-edge-connected graphs using a Hamiltonian path. We also give an algorithm that gives a 4/3-approximation for the TSP on (unweighted) cubic 3-edge-connected graphs.
