{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:45:51Z","timestamp":1725493551251},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_17","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"201-212","source":"Crossref","is-referenced-by-count":19,"title":["Approximation Hardness of TSP with Bounded Metrics"],"prefix":"10.1007","author":[{"given":"Lars","family":"Engebretsen","sequence":"first","affiliation":[]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"issue":"3","key":"17_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501\u2013555, 1998.","journal-title":"J. ACM"},{"key":"17_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/3-540-48523-6_17","volume-title":"Proc. 26th ICALP","author":"P. Berman","year":"1999","unstructured":"P. Berman and M. Karpinski. On some tighter inapproximability results. In Proc. 26th ICALP, vol. 1644 of LNCS, pp 200\u2013209, 1999."},{"key":"17_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/3-540-46541-3_32","volume-title":"Proc. 17th STACS","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"H.-J. B\u00f6ckenhauer, J. Hromkovi\u010d, R. Klasing, S. Seibert, and W. Unger. An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality. In Proc. 17th STACS, vol. 1770 of LNCS, pp 382\u2013391, 2000."},{"issue":"3","key":"17_CR4","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1051\/ita:2000115","volume":"34","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"H.-J. B\u00f6ckenhauer and S. Seibert. Improved lower bounds on the approximability of the traveling salesman problem. RAIRO Theoretical Informatics and Applications, 34(3):213\u2013255, 2000.","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"17_CR5","series-title":"Technical Report CS-93-13","volume-title":"Worst-case analysis of a new heuristic for the traveling salesman problem","author":"N. Christofides","year":"1976","unstructured":"N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report CS-93-13, GSIA, Carnegie Mellon University, 1976."},{"key":"17_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/3-540-49116-3_35","volume-title":"Proc. 16th STACS","author":"L. Engebretsen","year":"1999","unstructured":"L. Engebretsen. An explicit lower bound for TSP with distances one and two. In Proc. 16th STACS, vol. 1563 of LNCS, pp 373\u2013382, 1999."},{"issue":"1","key":"17_CR7","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/net.3230120103","volume":"12","author":"A. Frieze","year":"1982","unstructured":"A. Frieze, G. Galbiati, and F. Maffioli. On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks, 12(1):23\u201339, 1982.","journal-title":"Networks"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad. Some optimal inapproximability results. In Proc. 29th STOC, pp 1\u201310, 1997.","DOI":"10.1145\/258533.258536"},{"key":"17_CR9","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pp 85\u2013103. Plenum Press, New York, 1972."},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou and S. Vempala. On the approximability of the traveling salesman problem. In Proc. 32nd STOC, pp 126\u2013133, 2000.","DOI":"10.1145\/335305.335320"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou and S. Vempala. On the approximability of the traveling salesman problem. Manuscript, 2001.","DOI":"10.1145\/335305.335320"},{"issue":"1","key":"17_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C. H. Papadimitriou","year":"1993","unstructured":"C. H. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Math. of Oper. Res., 18(1):1\u201311, 1993.","journal-title":"Math. of Oper. Res."},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"L. Trevisan. When Hamming meets Euclid: The approximability of geometric TSP and MST. In Proc. 29th STOC, pp 21\u201329, 1997.","DOI":"10.1145\/258533.258541"},{"issue":"6","key":"17_CR14","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0020-0190(92)90103-3","volume":"44","author":"S. Vishwanathan","year":"1992","unstructured":"S. Vishwanathan. An approximation algorithm for the asymmetric travelling salesman problem with distances one and two. Inf. Process. Lett., 44(6):297\u2013302, 1992.","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T02:28:17Z","timestamp":1556936897000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}