{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:48:18Z","timestamp":1725475698653},"publisher-location":"Boston, MA","reference-count":21,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387346335"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-0-387-34735-6_21","type":"book-chapter","created":{"date-parts":[[2006,12,14]],"date-time":"2006-12-14T18:32:32Z","timestamp":1166121152000},"page":"251-270","source":"Crossref","is-referenced-by-count":20,"title":["Reusing Optimal TSP Solutions for Locally Modified Input Instances"],"prefix":"10.1007","author":[{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"first","affiliation":[]},{"given":"Luca","family":"Forlizzi","sequence":"additional","affiliation":[]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[]},{"given":"Joachim","family":"Kneis","sequence":"additional","affiliation":[]},{"given":"Joachim","family":"Kupke","sequence":"additional","affiliation":[]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Widmayer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.1024","volume":"38","author":"T. Andreae","year":"2001","unstructured":"T. Andreae: On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality. Networks 38, 2001, pp. 59\u201367.","journal-title":"Networks"},{"key":"21_CR2","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 parameterized triangle inequalities. SIAM Journal on Discrete Mathematics 8, 1995, pp. 1\u201316.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0020-0190(99)00160-X","volume":"73","author":"M. Bender","year":"2000","unstructured":"M. Bender, C. Chekuri: Performance guarantees for TSP with a parameterized triangle inequality. Information Processing Letters 73, 2000, pp. 17\u201321.","journal-title":"Information Processing Letters"},{"key":"21_CR4","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 sharpened triangle inequality. Information Processing Letters 75, 2000, pp. 133\u2013138.","journal-title":"Information Processing Letters"},{"key":"21_CR5","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, 2002, pp. 3\u201324.","journal-title":"Theoretical Computer Science"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"H.-J. B\u00f6ckenhauer, J. Hromkovi\u010d, J. Kneis, J. Kupke: On the parameterized approximability of TSP with deadlines. Theory of Computing Systems, to appear.","DOI":"10.1007\/s00224-007-1347-x"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"H.-J. B\u00f6ckenhauer, J. Hromkovi\u010d, J. Kneis, J. Kupke: On the approximation hardness of some generalizations of TSP. Proc. SWAT 2006, to appear.","DOI":"10.1007\/11785293_19"},{"key":"21_CR8","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. RAIRO Theoretical Informatics and Applications 34, 2000, pp. 213\u2013255.","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"21_CR9","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, Pittsburgh, 1976."},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"J.-F. Cordeau, G. Desaulniers, J. Desrosiers, M. M. Solomon, F. Soumis: VRP with time windows. In: P. Toth, D. Vigo (eds.): The Vehicle Routing Problem, SIAM 2001, pp. 157\u2013193.","DOI":"10.1137\/1.9780898718515.ch7"},{"issue":"1","key":"21_CR11","first-page":"31","volume":"1","author":"L. Forlizzi","year":"2006","unstructured":"L. Forlizzi, J. Hromkovi\u010d, G. Proietti, S. Seibert: On the stability of approximation for Hamiltonian path problems. Algorithmic Operations Research 1(1), 2006, pp. 31\u201345.","journal-title":"Algorithmic Operations Research"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"H. Greenberg: An annotated bibliography for post-solution analysis in mixed integer and combinatorial optimization. In: D. L. Woodruff (ed.): Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search, Kluwer Academic Publishers, 1998, pp. 97\u2013148.","DOI":"10.1007\/978-1-4757-2807-1_4"},{"key":"21_CR13","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/s004530010045","volume":"28","author":"N. Guttmann-Beck","year":"2000","unstructured":"N. Guttmann-Beck, R. Hassin, S. Khuller, B. Raghavachari: Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 28, 2000, pp. 422\u2013437.","journal-title":"Algorithmica"},{"key":"21_CR14","first-page":"178","volume":"10","author":"J. A. Hoogeveen","year":"1978","unstructured":"J. A. Hoogeveen: Analysis of Christofides\u2019 heuristic: Some paths are more difficult than cycles. Operations Research Letters 10, 1978, pp. 178\u2013193.","journal-title":"Operations Research Letters"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d: Stability of approximation algorithms for hard optimization problems. Proc. SOFSEM\u201999, Springer LNCS 1725, 1999, pp. 29\u201347.","DOI":"10.1007\/3-540-47849-3_2"},{"key":"21_CR16","unstructured":"J. Hromkovi\u010d: Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer 2003."},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0166-218X(91)90044-W","volume":"30","author":"M. Libura","year":"1991","unstructured":"M. Libura: Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems. Discrete Applied Mathematics 30, 1991, pp. 197\u2013211.","journal-title":"Discrete Applied Mathematics"},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0166-218X(98)00055-9","volume":"87","author":"M. Libura","year":"1998","unstructured":"M. Libura, E. S. van der Poort, G. Sierksma, J. A. A. van der Veen: Stability aspects of the traveling salesman problem based on k-best solutions. Discrete Applied Mathematics 87, 1998, pp. 159\u2013185.","journal-title":"Discrete Applied Mathematics"},{"key":"21_CR19","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1287\/opre.26.3.434","volume":"26","author":"Ch. Papadimitriou","year":"1978","unstructured":"Ch. Papadimitriou, K. Steiglitz: Some examples of difficult traveling salesman problems. Operations Research 26, 1978, pp. 434\u2013443.","journal-title":"Operations Research"},{"key":"21_CR20","doi-asserted-by":"publisher","first-page":"169 190","DOI":"10.1016\/0166-218X(93)E0126-J","volume":"58","author":"Y. N. Sotskov","year":"1995","unstructured":"Y. N. Sotskov, V. K. Leontev, E. N. Gordeev: Some concepts of stability analysis in combinatorial optimization. Discrete Appl. Math. 58, 1995, pp. 169 190.","journal-title":"Discrete Appl. Math."},{"key":"21_CR21","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0166-218X(98)00151-6","volume":"91","author":"S. Hoesel Van","year":"1999","unstructured":"S. Van Hoesel, A. Wagelmans: On the complexity of postoptimality analysis of 0\/1 programs. Discrete Applied Mathematics 91, 1999, pp. 251\u2013263.","journal-title":"Discrete Applied Mathematics"}],"container-title":["IFIP International Federation for Information Processing","Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-34735-6_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:50:28Z","timestamp":1619574628000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-0-387-34735-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9780387346335"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-34735-6_21","relation":{},"subject":[]}}