Shorter Tours by Nicer Ears:

7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs




Jens Vygen

Monday, February 11, 2013
4:00pm 5130
Upson Hall



We prove new results and obtain polynomial-time algorithms with improved approximation guarantees for the graphic traveling salesman problem and some related problems.

For the graphic TSP itself, we improve the approximation ratio to 7/5. For a generalization, the connected-$T$-join problem, we obtain the first nontrivial approximation algorithm, with ratio 3/2. This contains the graphic $s$-$t$-path-TSP as a special case. Our improved approximation guarantee for finding a smallest 2-edge-connected spanning subgraph is 4/3.

The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs. The same methods also provide the lower bounds (arising from LP relaxations) that we use to deduce the approximation ratios.

This is joint work with András Sebő.