{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T11:49:00Z","timestamp":1773143340069,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540775652","type":"print"},{"value":"9783540775669","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77566-9_5","type":"book-chapter","created":{"date-parts":[[2008,1,5]],"date-time":"2008-01-05T06:18:43Z","timestamp":1199513923000},"page":"50-65","source":"Crossref","is-referenced-by-count":36,"title":["On the Hardness of Reoptimization"],"prefix":"10.1007","author":[{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"first","affiliation":[]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[]},{"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Widmayer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1002\/net.10091","volume":"42","author":"C. Archetti","year":"2003","unstructured":"Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the traveling salesman problem. Networks\u00a042, 154\u2013159 (2003)","journal-title":"Networks"},{"key":"5_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/11785293_20","volume-title":"SWAT 2006","author":"G. Ausiello","year":"2006","unstructured":"Ausiello, G., Escoffier, B., Monnot, J., Paschos, V.Th.: Reoptimization of minimum and maximum traveling salesman\u2019s tours. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 196\u2013207. Springer, Heidelberg (2006)"},{"issue":"4","key":"5_CR3","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M.W. Bern","year":"1989","unstructured":"Bern, M.W., Plassmann, P.E.: The Steiner problem with edge lengths 1 and 2. Information Processing Letters\u00a032(4), 171\u2013176 (1989)","journal-title":"Information Processing Letters"},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-0-387-34735-6_21","volume-title":"IFIP TCS 2006","author":"H.-J. B\u00f6ckenhauer","year":"2006","unstructured":"B\u00f6ckenhauer, H.-J., Forlizzi, L., Hromkovi\u010d, J., Kneis, J., Kupke, J., Proietti, G., Widmayer, P.: Reusing optimal TSP solutions for locally modified input instances (extended abstract). In: IFIP TCS 2006. Proc.\u00a0of the 4th IFIP International Conference on Theoretical Computer Science, pp. 251\u2013270. Springer, Norwell (2006)"},{"issue":"2","key":"5_CR5","first-page":"83","volume":"2","author":"H.-J. B\u00f6ckenhauer","year":"2007","unstructured":"B\u00f6ckenhauer, H.-J., Forlizzi, L., Hromkovi\u010d, J., Kneis, J., Kupke, J., Proietti, G., Widmayer, P.: On the approximability of TSP on local modifications of optimally solved instances. Algorithmic Operations Research\u00a02(2), 83\u201393 (2007)","journal-title":"Algorithmic Operations Research"},{"key":"5_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/3-540-46521-9_7","volume-title":"CIAC 2000","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem (extended abstract). In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol.\u00a01767, pp. 72\u201386. Springer, Heidelberg (2000)"},{"key":"5_CR7","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":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: Approximation algorithms for TSP with sharpened triangle inequality. Information Processing Letters\u00a075, 133\u2013138 (2000)","journal-title":"Information Processing Letters"},{"key":"5_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/3-540-46541-3_32","volume-title":"STACS 2000","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality (extended abstract). In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 382\u2013394. Springer, Heidelberg (2000)"},{"key":"5_CR9","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":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Theoretical Computer Science\u00a0285, 3\u201324 (2002)","journal-title":"Theoretical Computer Science"},{"key":"5_CR10","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Kneis, J., Kupke, J.: On the parameterized approximability of TSP with deadlines. Theory of Computing Systems (to appear)"},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/11785293_19","volume-title":"SWAT 2006","author":"H.-J. B\u00f6ckenhauer","year":"2006","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Kneis, J., Kupke, J.: On the approximation hardness of some generalizations of TSP. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 184\u2013195. Springer, Heidelberg (2006)"},{"key":"5_CR12","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., M\u00f6mke, T., Rossmanith, P.: Reoptimization of Steiner trees: changing the terminal set (submitted)"},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1051\/ita:2000115","volume":"34","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Seibert, S.: Improved lower bounds on the approximability of the traveling salesman problem. RAIRO Theoretical Informatics and Applications\u00a034, 213\u2013255 (2000)","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"5_CR14","unstructured":"Christofides, N.: 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":"5_CR15","doi-asserted-by":"crossref","unstructured":"Cordeau, J.-F., Desaulniers, G., Desrosiers, J., Solomon, M.M., Soumis, F.: VRP with time windows. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem, SIAM 2001, pp. 157\u2013193 (2001)","DOI":"10.1137\/1.9780898718515.ch7"},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S.E. Dreyfus","year":"1971","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks\u00a01, 195\u2013207 (1971\/72)","journal-title":"Networks"},{"issue":"1","key":"5_CR17","first-page":"31","volume":"1","author":"L. Forlizzi","year":"2006","unstructured":"Forlizzi, L., Hromkovi\u010d, J., Proietti, G., Seibert, S.: On the stability of approximation for Hamiltonian path problems. Algorithmic Operations Research\u00a01(1), 31\u201345 (2006)","journal-title":"Algorithmic Operations Research"},{"key":"5_CR18","volume-title":"Computers and Intractability","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability. W. H. Freeman and Co., New York (1979)"},{"key":"5_CR19","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-1-4757-2807-1_4","volume-title":"Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search","author":"H. Greenberg","year":"1998","unstructured":"Greenberg, H.: An annotated bibliography for post-solution analysis in mixed integer and combinatorial optimization. In: Woodruff, D.L. (ed.) Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search, pp. 97\u2013148. Kluwer Academic Publishers, Dordrecht (1998)"},{"key":"5_CR20","first-page":"31","volume-title":"SIGACT News","author":"O. Goldreich","year":"2006","unstructured":"Goldreich, O.: Bravely, moderately - A common theme in four recent works. In: SIGACT News, vol.\u00a037, pp. 31\u201346. ACM, New York (2006)"},{"key":"5_CR21","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/s004530010045","volume":"28","author":"N. Guttmann-Beck","year":"2000","unstructured":"Guttmann-Beck, N., Hassin, R., Khuller, S., Raghavachari, B.: Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica\u00a028, 422\u2013437 (2000)","journal-title":"Algorithmica"},{"key":"5_CR22","first-page":"178","volume":"10","author":"J.A. Hoogeveen","year":"1978","unstructured":"Hoogeveen, J.A.: Analysis of Christofides\u2019 heuristic: Some paths are more difficult than cycles. Operations Research Letters\u00a010, 178\u2013193 (1978)","journal-title":"Operations Research Letters"},{"key":"5_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/3-540-47849-3_2","volume-title":"SOFSEM 1999","author":"J. Hromkovi\u010d","year":"1999","unstructured":"Hromkovi\u010d, J.: Stability of approximation algorithms for hard optimization problems. In: Bartosek, M., Tel, G., Pavelka, J. (eds.) SOFSEM 1999. LNCS, vol.\u00a01725, pp. 29\u201347. Springer, Heidelberg (1999)"},{"key":"5_CR24","volume-title":"Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics","author":"J. Hromkovi\u010d","year":"2003","unstructured":"Hromkovi\u010d, J.: Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, Heidelberg (2003)"},{"key":"5_CR25","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0166-218X(91)90044-W","volume":"30","author":"M. Libura","year":"1991","unstructured":"Libura, M.: Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems. Discrete Applied Mathematics\u00a030, 197\u2013211 (1991)","journal-title":"Discrete Applied Mathematics"},{"key":"5_CR26","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0166-218X(98)00055-9","volume":"87","author":"M. Libura","year":"1998","unstructured":"Libura, M., van der Poort, E.S., Sierksma, G., van der Veen, J.A.A.: Stability aspects of the traveling salesman problem based on k-best solutions. Discrete Applied Mathematics\u00a087, 159\u2013185 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"5_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/11672142_46","volume-title":"STACS 2006","author":"D. M\u00f6lle","year":"2006","unstructured":"M\u00f6lle, D., Richter, S., Rossmanith, P.: A faster algorithm for the Steiner tree problem. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 561\u2013570. Springer, Heidelberg (2006)"},{"key":"5_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-80291-0","volume-title":"The Steiner Tree Problem","author":"H.J. Pr\u00f6mel","year":"2002","unstructured":"Pr\u00f6mel, H.J., Steger, A.: The Steiner Tree Problem. Friedr.\u00a0Vieweg & Sohn, Braunschweig (2002)"},{"key":"5_CR29","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1287\/opre.26.3.434","volume":"26","author":"C.. Papadimitriou","year":"1978","unstructured":"Papadimitriou, Ch., Steiglitz, K.: Some examples of difficult traveling salesman problems. Operations Research\u00a026, 434\u2013443 (1978)","journal-title":"Operations Research"},{"key":"5_CR30","first-page":"770","volume-title":"Proc. of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms","author":"G. Robins","year":"2000","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: Proc. of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 770\u2013779. ACM, New York (2000)"},{"key":"5_CR31","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0166-218X(93)E0126-J","volume":"58","author":"Y.N. Sotskov","year":"1995","unstructured":"Sotskov, Y.N., Leontev, V.K., Gordeev, E.N.: Some concepts of stability analysis in combinatorial optimization. Discrete Appl.\u00a0Math.\u00a058, 169\u2013190 (1995)","journal-title":"Discrete Appl.\u00a0Math."},{"key":"5_CR32","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0166-218X(98)00151-6","volume":"91","author":"S. Hoesel Van","year":"1999","unstructured":"Van Hoesel, S., Wagelmans, A.: On the complexity of postoptimality analysis of 0\/1 programs. Discrete Applied Mathematics\u00a091, 251\u2013263 (1999)","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2008: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77566-9_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:45:05Z","timestamp":1619520305000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77566-9_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540775652","9783540775669"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77566-9_5","relation":{},"subject":[]}}