{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:22:02Z","timestamp":1725488522630},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_32","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T16:03:24Z","timestamp":1186070604000},"page":"382-394","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality"],"prefix":"10.1007","author":[{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"first","affiliation":[]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[]},{"given":"Sebastian","family":"Seibert","sequence":"additional","affiliation":[]},{"given":"Walter","family":"Unger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"issue":"5","key":"32_CR1","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"S. Arora: Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geometric Problems. J. ACM 45(5), 1998, pp. 753\u2013782.","journal-title":"J. ACM"},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora: Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In: Proc. 38th IEEE FOCS, 1997, pp. 554\u2013563.","DOI":"10.1007\/3-540-63248-4_5"},{"key":"32_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0895480192240226","volume":"8","author":"T. Andreae","year":"1995","unstructured":"T. Andreae, H.-J. Bandelt: Performance guarantees for approximation algorithms depending on parametrized triangle inequalities. SIAM J. Discr. Math. 8 (1995), pp. 1\u201316.","journal-title":"SIAM J. Discr. Math."},{"key":"32_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/3-540-48447-7_10","volume-title":"Proc. WADS\u201999","author":"M. A. Bender","year":"1999","unstructured":"M. A. Bender, C. Chekuri: Performance guarantees for the TSP with a parameterized triangle inequality. In: Proc. WADS\u201999, LNCS 1663, Springer 1999, pp. 80\u201385."},{"key":"32_CR5","series-title":"Lect Notes Comput Sci","volume-title":"Proc. CIAC 2000","author":"H.-J. B\u00f6ckenhauer","year":"1999","unstructured":"H.-J. B\u00f6ckenhauer, J. Hromkovi\u010d, R. Klasing, S. Seibert, W. Unger: Towards the Notion of Stability of Approximation Algorithms and the Traveling Salesman Problem. Extended abstract in: Proc. CIAC 2000, LNCS, to appear. Full version in: Electronic Colloquium on Computational Complexity, Report No. 31 (1999)."},{"key":"32_CR6","unstructured":"P. Berman, M. Karpinski: On some tighter inapproximability results. Technical Report TR98-029, Electronic Colloquium on Computational Complexity, 1998."},{"key":"32_CR7","series-title":"Technical Report","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 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, 1976."},{"key":"32_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/3-540-49116-3_35","volume-title":"Proc. STACS\u201999","author":"L. Engebretsen","year":"1999","unstructured":"L. Engebretsen: An explicit lower bound for TSP with distances one and two. Extended abstract in: Proc. STACS\u201999, LNCS 1563, Springer 1999, pp. 373\u2013382. Full version in: Electronic Colloquium on Computational Complexity, Revision 1 of Report No. 46 (1999)."},{"key":"32_CR9","unstructured":"J. Edmonds, E. L. Johnson: Matching: A Well-Solved Class of Integer Linear Programs. In: Proc. Calgary International Conference on Combinatorial Structures and Their Applications, Gordon and Breach 1970, pp. 89\u201392."},{"issue":"4","key":"32_CR10","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"H. N. Gabov","year":"1991","unstructured":"H. N. Gabov, R. E. Tarjan: Faster Scaling Algorithms for General Graph-Matching Problems. In: J. ACM 38(4), 1991, pp. 815\u2013853.","journal-title":"J. ACM"},{"key":"32_CR11","unstructured":"D. S. Hochbaum (Ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing Company 1996."},{"key":"32_CR12","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys (Eds.): The Traveling Salesman Problem. John Wiley & Sons, 1985."},{"key":"32_CR13","unstructured":"I. S. B. Mitchell: Guillotine subdivisions approximate polygonal subdivisions: Part II \u2014 a simple polynomial-time approximation scheme for geometric k-MST, TSP and related problems. Technical Report, Dept. of Applied Mathematics and Statistics, Stony Brook 1996."},{"key":"32_CR14","series-title":"Lect Notes Comput Sci","volume-title":"Lectures on Proof Verification and Approximation Algorithms","year":"1998","unstructured":"E. W. Mayr, H. J. Pr\u00f6mel, A. Steger (Eds.): Lectures on Proof Verification and Approximation Algorithms. LNCS 1967, Springer 1998."},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"Ch. Papadimitriou","year":"1993","unstructured":"Ch. Papadimitriou, M. Yannakakis: The traveling salesman problem with distances one and two. Mathematics of Operations Research 18 (1993), 1\u201311.","journal-title":"Mathematics of Operations Research"}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T18:03:05Z","timestamp":1578506585000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_32"}},"subtitle":["Extended Abstract"],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_32","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"24 March 2000","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}