{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T01:11:00Z","timestamp":1772068260329,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540671596","type":"print"},{"value":"9783540465218","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46521-9_7","type":"book-chapter","created":{"date-parts":[[2007,11,3]],"date-time":"2007-11-03T22:47:16Z","timestamp":1194130036000},"page":"72-86","source":"Crossref","is-referenced-by-count":14,"title":["Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem"],"prefix":"10.1007","author":[{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Seibert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Walter","family":"Unger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,2,14]]},"reference":[{"key":"7_CR1","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.1109\/SFCS.1997.646145"},{"key":"7_CR2","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. In: Journal of the ACM 45, No. 5 (Sep. 1998), pp. 753\u2013782.","journal-title":"Journal of the ACM"},{"key":"7_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":"7_CR4","unstructured":"D. P. Bovet, P. Crescenzi: Introduction to the Theory of Complexity, Prentice-Hall 1993."},{"key":"7_CR5","series-title":"Lect Notes Comput Sci","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, to appear."},{"key":"7_CR6","series-title":"Lect Notes Comput Sci","volume-title":"Proc. STACS\u201900","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"H.-J. B\u00f6ckenhauer, J. Hromkovi\u010d, R. Klasing, S. Seibert, W. Unger: An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality (Extended Abstract). In: Proc. STACS\u201900, LNCS, to appear."},{"key":"7_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":"7_CR8","doi-asserted-by":"crossref","unstructured":"S. A. Cook: The complexity of theorem proving procedures. In: Proc. 3rd ACM STOC, ACM 1971, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"7_CR9","unstructured":"P. Crescenzi, V. Kann: A compendium of NP optimization problems. http:\/\/www.nada.kth.se\/theory\/compendium\/"},{"key":"7_CR10","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest: Introduction to algorithms. MIT Press, 1990."},{"key":"7_CR11","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, Report TR98-046 (1999)."},{"key":"7_CR12","unstructured":"M. R. Garey, D. S. Johnson: Computers and vIntractability. A Guide to the Theory on NP-Completeness. W. H. Freeman and Company, 1979."},{"key":"7_CR13","unstructured":"J. H\u00e5stad: Some optimal inapproximability results. Extended abstract in: Proc. 29th ACM STOC, ACM 1997, pp. 1\u201310. Full version in: Electronic Colloquium on Computational Complexity, Report TR97-037, (1999)."},{"key":"7_CR14","unstructured":"D. S. Hochbaum (Ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing Company 1996."},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d: Stability of approximation algorithms and the knapsack problem. Unpublished manuscript, RWTH Aachen, 1998.","DOI":"10.1007\/978-3-642-60207-8_21"},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O. H. Ibarra","year":"1975","unstructured":"O. H. Ibarra, C. E. Kim: Fast approximation algorithms for the knapsack and sum of subsets problem. J. of the ACM 22 (1975), pp. 463\u2013468.","journal-title":"J. of the ACM"},{"key":"7_CR17","first-page":"256","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson: Approximation algorithms for combinatorial problems. JCSS 9 (1974), pp. 256\u2013278.","journal-title":"JCSS"},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz: On the ratio of the optimal integral and functional covers. Discrete Mathematics 13 (1975), pp. 383\u2013390.","journal-title":"Discrete Mathematics"},{"key":"7_CR19","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":"7_CR20","volume-title":"Guillotine subdivisions approximate polygonal subdivisions: Part II \u2014 a simple polynomial-time approximation scheme for geometric k-MST, TSP and related problems","author":"I. S. B. Mitchell","year":"1996","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":"7_CR21","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":"7_CR22","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"Ch. Papadimitriou","year":"1977","unstructured":"Ch. Papadimitriou: The Euclidean traveling salesman problem is NP-complete. Theoretical Computer Science 4 (1977), pp. 237\u2013244.","journal-title":"Theoretical Computer Science"},{"key":"7_CR23","unstructured":"Ch. Papadimitriou: Computational Complexity, Addison-Wesley 1994."},{"key":"7_CR24","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","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46521-9_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T04:44:29Z","timestamp":1556945069000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46521-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671596","9783540465218"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-46521-9_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}