{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T09:00:12Z","timestamp":1781341212047,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642450297","type":"print"},{"value":"9783642450303","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45030-3_53","type":"book-chapter","created":{"date-parts":[[2013,12,11]],"date-time":"2013-12-11T21:32:52Z","timestamp":1386797572000},"page":"568-578","source":"Crossref","is-referenced-by-count":19,"title":["New Inapproximability Bounds for TSP"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Lampis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Schmied","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"53_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof Verification and the Hardness of Approximation Problems. J. ACM\u00a045, 501\u2013555 (1998)","journal-title":"J. ACM"},{"key":"53_CR2","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M., Madry, A., Oveis Gharan, S., Saberi, A.: An O(logn\/ loglogn)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem. In: Proc. 21st SODA 2010, pp. 379\u2013389 (2010)","DOI":"10.1137\/1.9781611973075.32"},{"key":"53_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.\u00a01644, pp. 200\u2013209. Springer, Heidelberg (1999)"},{"key":"53_CR4","unstructured":"Berman, P., Karpinski, M.: Efficient Amplifiers and Bounded Degree Optimization, ECCC TR01-053 (2001)"},{"key":"53_CR5","unstructured":"Berman, P., Karpinski, M.: Improved Approximation Lower Bounds on Small Occurrence Optimization, ECCC TR03-008 (2003)"},{"key":"53_CR6","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: 8\/7-approximation algorithm for (1, 2)-TSP. In: Proc. 17th SODA 2006, pp. 641\u2013648 (2006)","DOI":"10.1145\/1109557.1109627"},{"key":"53_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-540-27821-4_6","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Bl\u00e4ser","year":"2004","unstructured":"Bl\u00e4ser, M.: A 3\/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 61\u201371. Springer, Heidelberg (2004)"},{"key":"53_CR8","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1051\/ita:2000115","volume":"34","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Seibert, S.: Improved Lower Bounds on the Approximability of the Traveling Salesman Problem. Theor. Inform. Appl.\u00a034, 213\u2013255 (2000)","journal-title":"Theor. Inform. Appl."},{"key":"53_CR9","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":"53_CR10","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\u00a035, 301\u2013318 (2003)","journal-title":"Algorithmica"},{"key":"53_CR11","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.\u00a072, 509\u2013546 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"53_CR12","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\u00a048, 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"53_CR13","unstructured":"Karpinski, M., Schmied, R.: On Approximation Lower Bounds for TSP with Bounded Metrics, CoRR arXiv: abs\/1201.5821 (2012)"},{"key":"53_CR14","unstructured":"Karpinski, M., Schmied, R.: On Improved Inapproximability Results for the Shortest Superstring and Related Problems. In: Proc. 19th CATS 2013. CRPIT, vol. 141, pp. 27\u201336 (2013)"},{"key":"53_CR15","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. Algorithms and Techniques","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.\u00a07408, pp. 243\u2013253. Springer, Heidelberg (2012)"},{"key":"53_CR16","doi-asserted-by":"crossref","unstructured":"M\u00f6mke, T., Svensson, O.: Approximating Graphic TSP by Matchings. In: Proc. IEEE 52nd FOCS 2011, pp. 560\u2013569 (2011)","DOI":"10.1109\/FOCS.2011.56"},{"key":"53_CR17","doi-asserted-by":"crossref","unstructured":"Mucha, M.: 13\/9-Approximation for Graphic TSP. In: Proc. STACS 2012, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. LIPIcs, vol.\u00a014, pp. 30\u201341 (2012)","DOI":"10.1007\/s00224-012-9439-7"},{"key":"53_CR18","doi-asserted-by":"crossref","unstructured":"Oveis Gharan, S., Saberi, A., Singh, M.: A Randomized Rounding Approach to the Traveling Salesman Problem. In: Proc. IEEE 52nd FOCS 2011, pp. 550\u2013559 (2011)","DOI":"10.1109\/FOCS.2011.80"},{"key":"#cr-split#-53_CR19.1","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C., Vempala, S.: On the Approximability of the Traveling Salesman Problem. In: Proc. 32nd ACM STOC 2000, pp. 126-133 (2000)","DOI":"10.1145\/335305.335320"},{"key":"#cr-split#-53_CR19.2","doi-asserted-by":"crossref","unstructured":"see also a corrected version in Combinatorica 26, 101-120 (2006)","DOI":"10.1007\/s00493-006-0008-z"},{"key":"53_CR20","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.\u00a018, 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"key":"53_CR21","unstructured":"Seb\u00f6, A., Vygen, J.: Shorter Tours by Nicer Ears, CoRR arXiv: abs\/1201.1870 (2012); to appear in Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45030-3_53","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T06:30:23Z","timestamp":1558765823000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45030-3_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450297","9783642450303"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45030-3_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}