Computer Science – Data Structures and Algorithms
Scientific paper
2011-04-15
Computer Science
Data Structures and Algorithms
20 pages, 7 figures
Scientific paper
We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost. For the TSP on graphic metrics (graph-TSP), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework allows for generalizations in a natural way and also leads to a 1.586-approximation algorithm for the traveling salesman path problem on graphic metrics where the start and end vertices are prespecified.
Mömke Tobias
Svensson Ola
No associations
LandOfFree
Approximating Graphic TSP by Matchings 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 Approximating Graphic TSP by Matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating Graphic TSP by Matchings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-9109