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.
Accepté le :
DOI : 10.1051/ro/2014062
Mots-clés : Traveling Salesman Problem, Approximability
@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ro/2014062/
P. Berman and M. Karpinski, On some tighter inapproximability results, in Proc. of 26th ICALP, LNCS 1644 (1999) 200–209. | MR
P. Berman and M. Karpinski, Improved Approximation lower bounds on small occurrence optimization, ECCC TR03-008 (2003).
P. Berman and M. Karpinski, -approximation algorithm for -TSP, in Proc. of 17th SODA (2006) 641–648. | MR | Zbl
S. Boyd, R. Sitters, S. van der Ster and L. Stougie, TSP on cubic and subcubic graphs, in Proc. of 15th IPCO. Lect. Notes Comput. Sci. 6655 (2011) 65–77. | MR | Zbl
S. Boyd, R. Sitters, S. van der Ster and L. Stougie, TSP on cubic and subcubic graphs. Math. Program (2011) 227–245. | Zbl
N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem, Technical Report CS-93-13. Carnegie Mellon University, Pittsburgh (1976).
B. Csaba, M. Karpinski and P. Krysta, Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems, in Proc. of 13th ACM-SIAM SODA (2002) 74–83. | Zbl
J. Correa, O. Larré and J. Soto, TSP tours in cubic graphs: Beyond , in Proc. of 20th ESA. Lect. Notes Comput. Sci. 7501 (2012) 790–801. | Zbl
and , TSP with bounded metrics. J. Comput. Syst. Sci. 72 (2006) 509–546. | DOI | Zbl
, and , An improved upper bound for the TSP in cubic 3-edge-connected graphs. Oper. Res. Lett. 33 (2005) 467–474. | DOI | Zbl
, and , The planar hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5 (1976) 704–714. | DOI | Zbl
, Some optimal inapproximability results. J. ACM 48 (2001) 798–859. | DOI | Zbl
M. Karpinski, M. Lampis and R. Schmied, New inapproximability bounds for TSP, in Proc. of 24th ISAAC. Lect. Notes Comput. Sci. 8283 (2013) 568–578.
and , On approximation lower bounds for TSP with bounded metrics. Electron Colloq. Comput. Complexity 19 (2012).
M. Karpinski and R. Schmied, On improved inapproximability results for the shortest superstring and related problems, in Proc. of 19th CATS CRPIT 141 (2013) 27–36.
T. Mömke and O. Svensson, Approximating graphic TSP by matchings, in Proc. of IEEE 52nd FOCS (2011) 560–569. | Zbl
M. Mucha, -Approximation for graphic TSP, in Proc. of STACS, Vol. 14 of LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2012) 30–41. | Zbl
S. Oveis Gharan, A. Saberi and M. Singh, A Randomized Rounding Approach to the Traveling Salesman Problem, in Proc. of IEEE 52nd FOCS (2011) 550–559. | Zbl
and , The traveling salesman problem with distances one and two. Math. Oper. Res. 18 (1993) 1–11. | DOI | Zbl
and , Shorter tours by nicer ears. Combinatorica 34 (2014) 597–629. | DOI | Zbl
Cité par Sources :
