2013/04/25 by Marek Karpinski, Karpinski, Marek, Richard Schmied +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.CC #cs.DM #cs.DS #math.CO #math.OC
paper · pdf · doi:10.48550/arxiv.1304.6800
arxiv created 2013/05/14 · arxiv updated 2013/05/15
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.