Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2015 Copyright 2015 University of Bonn, Department of Computer Science, Abt. V
85359

15.09.2015

Approximability of TSP on Power Law Graphs
Mikael Gast, Mathias Hauptmann and Marek Karpinski
[Download PostScript] [Download PDF]

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.

Last Change: 09/15/15 at 07:37:33
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V