Computer Science – Discrete Mathematics
Scientific paper
2012-01-09
Computer Science
Discrete Mathematics
Scientific paper
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 (arising from LP relaxations) that we use to deduce the approximation ratios.
Seb\Hö András
Vygen Jens
No associations
LandOfFree
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 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with 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, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 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 will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-643870