Issue |
RAIRO-Oper. Res.
Volume 49, Number 4, October-December 2015
|
|
---|---|---|
Page(s) | 651 - 668 | |
DOI | https://doi.org/10.1051/ro/2014062 | |
Published online | 27 March 2015 |
Approximation hardness of graphic TSP on cubic graphs
1 Deptartement of Computer Science and the Hausdorff Center for
Mathematics, University of Bonn. Supported in part by DFG Grants and the Hausdorff Grant
EXC59-1/2
marek@cs.uni-bonn.de
2 Deptartement of Computer Science, University of Bonn. Work
supported by Hausdorff Doctoral Fellowship
schmied@cs.uni-bonn.de
Received:
19
March
2014
Accepted:
8
December
2014
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 result on the Graphic TSP for cubic graphs is the first known inapproximability result on that problem. The proof technique in this paper 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.
Mathematics Subject Classification: 68W25 / 68W40
Key words: Traveling Salesman Problem / Approximability
© EDP Sciences, ROADEF, SMAI 2015
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.