Exécution de notre outil de synthèse sur un nouvel article

Vérifiez l’article ci-dessous, puis lancez sa synthèse.


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

András Sebő, Jens Vygen

Résumé : We prove new results for approximating the graphic TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees. 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 necessary to deduce the approximation ratios. Since all our lower bounds arise from the classical LP relaxations, we also obtain the same new bounds on their integrality gaps.

Soumis à arXiv le 09 Jan. 2012