{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:27:02Z","timestamp":1725460022156},"publisher-location":"Boston","reference-count":28,"publisher":"Kluwer Academic Publishers","isbn-type":[{"type":"print","value":"1402081405"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/1-4020-8141-3_2","type":"book-chapter","created":{"date-parts":[[2006,2,21]],"date-time":"2006-02-21T15:15:11Z","timestamp":1140534911000},"page":"3-18","source":"Crossref","is-referenced-by-count":1,"title":["Stability of Approximation in Discrete Optimization"],"prefix":"10.1007","author":[{"given":"Juraj","family":"Hromkovi\u010d","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora: Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In: Proc. 37th IEEE FOCS, IEEE 1996, pp. 2\u201311.","DOI":"10.1109\/SFCS.1996.548458"},{"key":"2_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, IEEE 1997, pp. 554\u2013563.","DOI":"10.1109\/SFCS.1997.646145"},{"key":"2_CR3","unstructured":"D. P. Bovet, C. Crescenzi: Introduction to the Theory of Complexity, Prentice-Hall 1993."},{"key":"2_CR4","series-title":"Technical Report","volume-title":"Worst-case analysis of a new heuristic for the travelling salesman problem","author":"N. Christofides","year":"1976","unstructured":"N. Christofides: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsbourgh, 1976."},{"key":"2_CR5","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":"2_CR6","unstructured":"M. R. Garey, D. S. Johnson: Computers and Intractibility. A Guide to the Theory on NP-Completeness. W. H. Freeman and Company, 1979."},{"key":"2_CR7","unstructured":"D. S. Hochbaum (Ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing Company 1996."},{"key":"2_CR8","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":"2_CR9","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":"2_CR10","doi-asserted-by":"crossref","unstructured":"R. M. Karp: Reducibility among combinatorial problems. In: R. E. Miller, J. W. Thatcher (eds.): Complexity of Computer Computations, Plenum Press 1972, pp. 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"2_CR11","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lovasz","year":"1975","unstructured":"L. Lovasz: On the ratio of the optimal integral and functional covers. Discrete Mathematics 13 (1975), pp. 383\u2013390.","journal-title":"Discrete Mathematics"},{"key":"2_CR12","series-title":"Technical Report","volume-title":"Guillotine subdivisions approximate polygonal subdivisions: Part II\u2014a 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\u2014a 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":"2_CR13","doi-asserted-by":"crossref","unstructured":"E. W. Mayr, H. J. Promel, A. Steger (Eds.): Lecture on Proof Verification and Approximation Algorithms. Lecture Notes in Computer Science 1967, Springer 1998.","DOI":"10.1007\/BFb0053010"},{"key":"2_CR14","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 travelling salesman problem is NP-complete. Theoretical Computer Science 4 (1977), pp. 237\u2013244.","journal-title":"Theoretical Computer Science"},{"key":"2_CR15","unstructured":"Ch. Papadimitriou: Computational Complexity, Addison-Wesley 1994."},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"I. Wegener: Theoretische Informatik: eine algorithmenorientierte Einfuhrung. B. G. Teubner 1993.","DOI":"10.1007\/978-3-322-94687-4"},{"key":"2_CR17","unstructured":"J. Hromkovi\u010d: Theoretical Computer Science, Springer-Verlag 2004."},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"H.-J. B\u00f6ckenhauer, D. Bongartz, J. Hromkovi\u010d R. Klasing, G. Proietti, S. Seibert, W. Unger: On the Hardness of constructing mininal 2-connected spanning subgraphs in complete graphs with sharped triangle inequality. In: Proc FSTTCS?02, pp.59\u201370.","DOI":"10.1007\/3-540-36206-1_7"},{"key":"2_CR19","unstructured":"J. Hromkovi\u010d: Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer-Verlag 2003."},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"V. V. Vazirani: Approximation Algorithms. Springer-Verlag 2003.","DOI":"10.1007\/978-3-662-04565-7"},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R. G. Downey","year":"1995","unstructured":"R. G. Downey, M. R. Fellows: Fixed-parameter tractibility and completeness I: Basic Results. SIAM Journal of Computing. 24 (1995), pp. 873\u2013921.","journal-title":"SIAM Journal of Computing"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"R. G. Downey, M. R. Fellows: Parametrized Complexity. Springer-Verlag 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"2_CR23","unstructured":"L. Forlizzi, J. Hromkovi\u010d G. Proietti, S. Seibert: On the stability of approximation for Hamiltonian path problems. Unpublished manuscript."},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0020-0190(00)00089-2","volume":"75","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"H.-J. B\u00f6ckenhauer, J. Hromkovi\u010d R. Klasing, S. Seibert, W. Unger: Approximation algorithms for TSP with sharped triangle inequality. Information Processing Letters. 75 (2000), pp. 133\u2013138.","journal-title":"Information Processing Letters"},{"key":"2_CR25","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, S. Seibert: Improved lower bounds on the approximability of the traveling salesman problem. Theoretical Informatics and Applications. 34 (2000), pp.213\u2013255.","journal-title":"Theoretical Informatics and Applications"},{"issue":"1","key":"2_CR26","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 guarentees for approximation algorithms depending on parametrized triangle inequalities. SIAM Journal on Discrete Mathematics. 8(1), pp. 1\u201316, February 1995.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"2_CR27","unstructured":"M. Bender, C. Chekuri: Performance guarentees for TSP with a parametrized triangle inequality. In: Proc. 6. International Workshop on Algorithms and Data Structures, WADS?99, volume 1663 Lecture Notes in Computer Science. pp. 1\u201316, Springer, August 1999."},{"issue":"1","key":"2_CR28","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(01)00287-0","volume":"285","author":"H.-J. B\u00f6ckenhauer","year":"2002","unstructured":"H.-J. B\u00f6ckenhauer, J. Hromkovi\u010d R. Klasing, S. Seibert, W. Unger: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Theoretical Computer Science. 285(1), pp. 3\u201324, July 2002.","journal-title":"Theoretical Computer Science"}],"container-title":["IFIP International Federation for Information Processing","Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/1-4020-8141-3_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:28:10Z","timestamp":1619555290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/1-4020-8141-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["1402081405"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/1-4020-8141-3_2","relation":{},"subject":[]}}