SHORTER TOURS BY NICER EARS: 7/5-APPROXIMATION FOR THE GRAPH-TSP, 3/2 FOR THE PATH VERSION, AND 4/3 FOR TWO-EDGE-CONNECTED SUBGRAPHS

摘要

We prove new results for approximating the graph-TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees. For the graph-TSP itself, we improve the approximation ratio to 7/5. For a generalization, the minimum T-tour problem, we obtain the rst nontrivial approximation algorithm, with ratio 3/2. This contains the s-t-path graph-TSP as a special case. Our approximation guarantee for nding 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.