2015/09/14 by Mikael Gast, Gast, Mikael, Mathias Hauptmann +3
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.1509.03976
arxiv created 2015/09/14 · arxiv updated 2015/09/15
In this paper we study the special case of Graphic TSP where the underlying graph is a power law graph (PLG). We give a refined analysis of some of the current best approximation algorithms and show that an improved approximation ratio can be achieved for certain ranges of the power law exponent β. For the value of power law exponent β=1.5 we obtain an approximation ratio of 1.34 for Graphic TSP. Moreover we study the (1,2)-TSP with the underlying graph of 1-edges being a PLG. We show improved approximation ratios in the case of underlying deterministic PLGs for β greater than 1.666. For underlying random PLGs we further improve the analysis and show even better expected approximation ratio for the range of β between 1 and 3.5. On the other hand we prove the first explicit inapproximability bounds for (1,2)-TSP for an underlying power law graph.