Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2015 Copyright 2015 Universität Bonn, Institut für Informatik, Abt. V


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
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope