TR13-066 | 25th April 2013 07:40
Approximation Hardness of Graphic TSP on Cubic Graphs
TR13-066
Authors:
Marek Karpinski,
Richard Schmied
Publication: 25th April 2013 09:25
Downloads: 3290
Keywords:
(1,2)-TSP,
Approximation Algorithms,
Approximation Hardness,
Approximation Lower Bounds,
Bounded Degree Amplifiers,
Bounded Metrics,
Cubic and Subcubic Instances,
Graphic TSP,
Hybrid Problem,
Simulating Gadgets,
Traveling Salesman Problem
Abstract:
We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well as the new inapproximability bounds for the corresponding instances of the (1,2)-TSP. The proof technique uses new modular constructions of simulating gadgets for the restricted cubic and subcubic instances. The modular constructions used in the paper could be also of independent interest.
