{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T05:34:55Z","timestamp":1743140095959,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319221762"},{"type":"electronic","value":"9783319221779"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-22177-9_1","type":"book-chapter","created":{"date-parts":[[2015,8,3]],"date-time":"2015-08-03T10:05:43Z","timestamp":1438596343000},"page":"3-11","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,4]]},"reference":[{"key":"1_CR1","unstructured":"Approximation Taxonomy of Metric TSP (2015). http:\/\/theory.cs.uni-bonn.de\/info5\/tsp"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M., M\u0105dry, A., Gharan, S., Saberi, A.: An \n$$O(\\log n\/ \\log \\log n)$$\n-approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of the 21st SODA, pp. 379\u2013389 (2010)","DOI":"10.1137\/1.9781611973075.32"},{"key":"1_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-48523-6_17","volume-title":"Automata, Languages and Programming","author":"P Berman","year":"1999","unstructured":"Berman, P., Karpinski, M.: On some tighter inapproximability results. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, p. 200. Springer, Heidelberg (1999)"},{"key":"1_CR4","unstructured":"Berman, P., Karpinski, M.: Efficient amplifiers and bounded degree optimization. ECCC TR01-053 (2001)"},{"key":"1_CR5","unstructured":"Berman, P., Karpinski, M.: Improved approximation lower bounds on small occurrence optimization. ECCC TR03-008 (2003)"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: 8\/7-approximation algorithm for \n$$(1, 2)$$\n-TSP. In: Proceedings of the 17th SODA, pp. 641\u2013648 (2006)","DOI":"10.1145\/1109557.1109627"},{"key":"1_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-642-20807-2_6","volume-title":"Integer Programming and Combinatoral Optimization","author":"S Boyd","year":"2011","unstructured":"Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: TSP on cubic and subcubic graphs. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 65\u201377. Springer, Heidelberg (2011)"},{"key":"1_CR8","unstructured":"Christofides, N.: Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem, Technical Report CS-93-13. Carnegie Mellon University, Pittsburgh (1976)"},{"key":"1_CR9","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s00453-002-1001-6","volume":"35","author":"L Engebretsen","year":"2003","unstructured":"Engebretsen, L.: An explicit lower bound for TSP with distances one and two. Algorithmica 35, 301\u2013318 (2003)","journal-title":"Algorithmica"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1016\/j.jcss.2005.12.001","volume":"72","author":"L Engebretsen","year":"2006","unstructured":"Engebretsen, L., Karpinski, M.: TSP with bounded metrics. J. Comput. Syst. Sci. 72, 509\u2013546 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48, 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1145\/1082036.1082041","volume":"52","author":"H Kaplan","year":"2005","unstructured":"Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM 52, 602\u2013626 (2005)","journal-title":"J. ACM"},{"key":"1_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/3-540-44669-9_4","volume-title":"Fundamentals of Computation Theory","author":"M Karpinski","year":"2001","unstructured":"Karpinski, M.: Approximating bounded degree instances of NP-hard problems. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol. 2138, p. 24. Springer, Heidelberg (2001)"},{"key":"1_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/978-3-642-45030-3_53","volume-title":"Algorithms and Computation","author":"M Karpinski","year":"2013","unstructured":"Karpinski, M., Lampis, M., Schmied, R.: New inapproximability bounds for TSP. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 568\u2013578. Springer, Heidelberg (2013)"},{"key":"1_CR15","unstructured":"Karpinski, M., Schmied, R.: On approximation lower bounds for TSP with bounded metrics. CoRR abs\/1201.5821 (2012)"},{"key":"1_CR16","unstructured":"Karpinski, M., Schmied, R.: Improved lower bounds for the shortest superstring and related problems. In: Proceedings 19th CATS, CRPIT 141, pp. 27\u201336 (2013)"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Schmied, R.: Approximation hardness of graphic TSP on cubic graphs, CoRR abs\/1304.6800, 2013. Journal version RAIRO-Operations Research 49, pp. 651\u2013668 (2015)","DOI":"10.1051\/ro\/2014062"},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-642-32512-0_21","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"M Lampis","year":"2012","unstructured":"Lampis, M.: Improved inapproximability for TSP. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX 2012 and RANDOM 2012. LNCS, vol. 7408, pp. 243\u2013253. Springer, Heidelberg (2012)"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"M\u00f6mke, T., Svensson, O.: Approximating graphic TSP by matchings. In: Proceedings of the IEEE 52nd FOCS, pp. 560\u2013569 (2011)","DOI":"10.1109\/FOCS.2011.56"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/s00493-006-0008-z","volume":"26","author":"C Papadimitriou","year":"2006","unstructured":"Papadimitriou, C., Vempala, S.: On the approximability of the traveling salesman problem. Combinatorica 26, 101\u2013120 (2006)","journal-title":"Combinatorica"},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C Papadimitriou","year":"1993","unstructured":"Papadimitriou, C., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18, 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00493-014-2779-y","volume":"34","author":"A Seb\u0151","year":"2014","unstructured":"Seb\u0151, A., Vygen, J.: Shorter tours by nicer ears: 7\/5-approximation for the Graph-TSP, 3\/2 for the Path Version, and 4\/3 for two-edge-connected subgraphs. Combinatorica 34, 1\u201334 (2014)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-22177-9_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T14:15:51Z","timestamp":1675865751000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-22177-9_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319221762","9783319221779"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-22177-9_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"4 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}