Approximation hardness of graphic TSP on cubic graphs

Karpinski, Marek; Schmied, Richard

doi:10.1051/ro/2014062

Karpinski, Marek ¹ ; Schmied, Richard ²

¹ 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
² 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.

Résumé

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 : 2014-03-19
Accepté le : 2014-12-08

MR Zbl

DOI : 10.1051/ro/2014062

Classification : 68W25, 68W40
Mots clés : Traveling Salesman Problem, Approximability

Affiliations des auteurs :

Karpinski, Marek ¹ ; Schmied, Richard ²

@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/

Bibliographie
Cité par

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, $8 / 7$ -approximation algorithm for $(1, 2)$ -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 $4 / 3$ , in Proc. of 20th ESA. Lect. Notes Comput. Sci. 7501 (2012) 790–801. | Zbl

L. Engebretsen and M. Karpinski, TSP with bounded metrics. J. Comput. Syst. Sci. 72 (2006) 509–546. | DOI | Zbl

D. Gamarnik, M. Lewenstein and M. Sviridenko, An improved upper bound for the TSP in cubic 3-edge-connected graphs. Oper. Res. Lett. 33 (2005) 467–474. | DOI | Zbl

M. Garey, D. Johnson and R. Tarjan, The planar hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5 (1976) 704–714. | DOI | Zbl

J. Håstad, 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.

M. Karpinski and R. Schmied, 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, $13 / 9$ -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

C. Papadimitriou and M. Yannakakis, The traveling salesman problem with distances one and two. Math. Oper. Res. 18 (1993) 1–11. | DOI | Zbl

A. Sebö and J. Vygen, Shorter tours by nicer ears. Combinatorica 34 (2014) 597–629. | DOI | Zbl

Cité par Sources :