Computer Science – Data Structures and Algorithms
Scientific paper
2011-07-06
Computer Science
Data Structures and Algorithms
Scientific paper
We study the Travelling Salesman Problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem is of interest because of its relation to the famous 4/3 conjecture for metric TSP, which says that the integrality gap, i.e., the worst case ratio between the optimal values of the TSP and its linear programming relaxation (the subtour elimination relaxation), is 4/3. We present the first algorithm for cubic graphs with approximation ratio 4/3. The proof uses polyhedral techniques in a surprising way, which is of independent interest. In fact we prove constructively that for any cubic graph on $n$ vertices a tour of length 4n/3-2 exists, which also implies the 4/3 conjecture, as an upper bound, for this class of graph-TSP. Recently, M\"omke and Svensson presented a randomized algorithm that gives a 1.461-approximation for graph-TSP on general graphs and as a side result a 4/3-approximation algorithm for this problem on subcubic graphs, also settling the 4/3 conjecture for this class of graph-TSP. We will present a way to derandomize their algorithm which leads to a smaller running time than the obvious derandomization. All of the latter also works for multi-graphs.
Boyd Sylvia
der Ster Suzanne van
Sitters Rene
Stougie Leen
No associations
LandOfFree
The traveling salesman problem on cubic and subcubic graphs 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 The traveling salesman problem on cubic and subcubic graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The traveling salesman problem on cubic and subcubic graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-677767