{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T14:28:32Z","timestamp":1784557712772,"version":"3.55.0"},"reference-count":20,"publisher":"EDP Sciences","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1051\/ro\/2014062","type":"journal-article","created":{"date-parts":[[2015,1,7]],"date-time":"2015-01-07T13:55:50Z","timestamp":1420638950000},"page":"651-668","source":"Crossref","is-referenced-by-count":6,"title":["Approximation hardness of graphic TSP on cubic graphs"],"prefix":"10.1051","volume":"49","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Schmied","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"250","published-online":{"date-parts":[[2015,3,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"P. Berman and M. Karpinski, On some tighter inapproximability results, inProc. of 26th ICALP, LNCS1644(1999) 200\u2013209.","DOI":"10.1007\/3-540-48523-6_17"},{"key":"R2","unstructured":"P. Berman and M. Karpinski,Improved Approximation lower bounds on small occurrence optimization, ECCC TR03-008 (2003)."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"P. Berman and M. Karpinski, 8 \/ 7-approximation algorithm for (1,2)-TSP, inProc. of 17th SODA(2006) 641\u2013648.","DOI":"10.1145\/1109557.1109627"},{"key":"R4","unstructured":"S. Boyd, R. Sitters, S. van der Ster and L. Stougie, TSP on cubic and subcubic graphs, inProc. of 15th IPCO. Lect. Notes Comput. Sci.6655(2011) 65\u201377."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"S. Boyd, R. Sitters, S. van der Ster and L. Stougie,TSP on cubic and subcubic graphs.Math. Program(2011) 227\u2013245.","DOI":"10.1007\/s10107-012-0620-1"},{"key":"R6","unstructured":"N. Christofides,Worst-case analysis of a new heuristic for the traveling salesman problem, Technical Report CS-93-13. Carnegie Mellon University, Pittsburgh (1976)."},{"key":"R7","unstructured":"B. Csaba, M. Karpinski and P. Krysta, Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems, inProc. of 13th ACM-SIAM SODA(2002) 74\u201383."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"J. Correa, O. Larr\u00e9 and J. Soto, TSP tours in cubic graphs: Beyond 4 \/ 3, inProc. of 20th ESA. Lect. Notes Comput. Sci.7501(2012) 790\u2013801.","DOI":"10.1007\/978-3-642-33090-2_68"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Engebretsen L. and Karpinski M., TSP with bounded metrics.J. Comput. Syst. Sci.72(2006) 509\u2013546.","DOI":"10.1016\/j.jcss.2005.12.001"},{"key":"R10","unstructured":"Gamarnik D., Lewenstein M. and Sviridenko M., An improved upper bound for the TSP in cubic 3-edge-connected graphs.Oper. Res. Lett.33(2005) 467\u2013474."},{"key":"R11","unstructured":"Garey M., Johnson D. and Tarjan R., The planar hamiltonian circuit problem is NP-complete.SIAM J. Comput.5(1976) 704\u2013714."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"H\u00e5stad J., Some optimal inapproximability results.J. ACM48(2001) 798\u2013859.","DOI":"10.1145\/502090.502098"},{"key":"R13","unstructured":"M. Karpinski, M. Lampis and R. Schmied, New inapproximability bounds for TSP, inProc. of 24th ISAAC. Lect. Notes Comput. Sci.8283(2013) 568\u2013578."},{"key":"R14","unstructured":"Karpinski M. and Schmied R., On approximation lower bounds for TSP with bounded metrics.Electron Colloq. Comput. Complexity19(2012)."},{"key":"R15","unstructured":"M. Karpinski and R. Schmied, On improved inapproximability results for the shortest superstring and related problems, inProc. of 19th CATS CRPIT141(2013) 27\u201336."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"T. M\u00f6mke and O. Svensson, Approximating graphic TSP by matchings, inProc. of IEEE 52nd FOCS(2011) 560\u2013569.","DOI":"10.1109\/FOCS.2011.56"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"M. Mucha, 13 \/ 9-Approximation for graphic TSP, inProc. of STACS, Vol. 14of LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2012) 30\u201341.","DOI":"10.1007\/s00224-012-9439-7"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"S. Oveis Gharan, A. Saberi and M. Singh, A Randomized Rounding Approach to the Traveling Salesman Problem, inProc. of IEEE 52nd FOCS(2011) 550\u2013559.","DOI":"10.1109\/FOCS.2011.80"},{"key":"R19","unstructured":"Papadimitriou C. and Yannakakis M., The traveling salesman problem with distances one and two.Math. Oper. Res.18(1993) 1\u201311."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Seb\u00f6 A. and Vygen J., Shorter tours by nicer ears.Combinatorica34(2014) 597\u2013629.","DOI":"10.1007\/s00493-014-2960-3"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2014062\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,19]],"date-time":"2019-08-19T10:38:39Z","timestamp":1566211119000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2014062"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,27]]},"references-count":20,"journal-issue":{"issue":"4"},"alternative-id":["ro140062"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2014062","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,27]]}}}