Geodesic
Approximation hardness of graphic TSP on cubic graphs
Karpinski, Marek1 ; Schmied, Richard2
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 
2 Deptartement of Computer Science, University of Bonn. Work supported by Hausdorff Doctoral Fellowship 
RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 4, pp. 651-668

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2014062
Classification : 68W25, 68W40
Keywords: Traveling Salesman Problem, Approximability

Karpinski, Marek 1 ; Schmied, Richard 2

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 
2 Deptartement of Computer Science, University of Bonn. Work supported by Hausdorff Doctoral Fellowship  
@article{RO_2015__49_4_651_0,
     author = {Karpinski, Marek and Schmied, Richard},
     title = {Approximation hardness of graphic {TSP} on cubic graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {651--668},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {4},
     year = {2015},
     doi = {10.1051/ro/2014062},
     mrnumber = {3350130},
     zbl = {1341.68308},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2014062/}
}
TY  - JOUR
AU  - Karpinski, Marek
AU  - Schmied, Richard
TI  - Approximation hardness of graphic TSP on cubic graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2015
SP  - 651
EP  - 668
VL  - 49
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2014062/
DO  - 10.1051/ro/2014062
LA  - en
ID  - RO_2015__49_4_651_0
ER  - 
%0 Journal Article
%A Karpinski, Marek
%A Schmied, Richard
%T Approximation hardness of graphic TSP on cubic graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2015
%P 651-668
%V 49
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2014062/
%R 10.1051/ro/2014062
%G en
%F RO_2015__49_4_651_0
Karpinski, Marek; Schmied, Richard. Approximation hardness of graphic TSP on cubic graphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 4, pp. 651-668. doi: 10.1051/ro/2014062

Cité par Sources :