{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:42:50Z","timestamp":1725586970214},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642199998"},{"type":"electronic","value":"9783642200007"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20000-7_2","type":"book-chapter","created":{"date-parts":[[2011,6,21]],"date-time":"2011-06-21T03:27:21Z","timestamp":1308626841000},"page":"7-15","source":"Crossref","is-referenced-by-count":4,"title":["Knowing All Optimal Solutions Does Not Help for TSP Reoptimization"],"prefix":"10.1007","author":[{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"first","affiliation":[]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[]},{"given":"Andreas","family":"Sprock","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","series-title":"An EATCS Series","volume-title":"Texts in Theoretical Computer Science","author":"J. Hromkovi\u010d","year":"2003","unstructured":"Hromkovi\u010d, J.: Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. In: Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2003)"},{"issue":"3","key":"2_CR2","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"Sahni, S., Gonzalez, T.F.: P-complete approximation problems. Journal of the ACM\u00a023(3), 555\u2013565 (1976)","journal-title":"Journal of the ACM"},{"issue":"1-2","key":"2_CR3","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(96)00042-X","volume":"72","author":"M.W. Sch\u00e4ffter","year":"1997","unstructured":"Sch\u00e4ffter, M.W.: Scheduling with forbidden sets. Discrete Applied Mathematics\u00a072(1-2), 155\u2013166 (1997)","journal-title":"Discrete Applied Mathematics"},{"issue":"1-3","key":"2_CR4","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(1-3), 251\u2013263 (1999)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"2_CR5","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(3), 154\u2013159 (2003)","journal-title":"Networks"},{"key":"2_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/11785293_20","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"G. Ausiello","year":"2006","unstructured":"Ausiello, G., Escoffier, B., Monnot, J., Paschos, V.T.: 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)"},{"key":"2_CR7","series-title":"IFIP","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-0-387-34735-6_21","volume-title":"Proc.\u00a0of the 4th IFIP International Conference on Theoretical Computer Science (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: Navarro, G., Bertossi, L.E., Kohayakawa, Y. (eds.) Proc.\u00a0of the 4th IFIP International Conference on Theoretical Computer Science (TCS 2006). IFIP, vol.\u00a0209, pp. 251\u2013270. Springer, New York (2006)"},{"key":"2_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/978-3-540-85238-4_12","volume-title":"Mathematical Foundations of Computer Science 2008","author":"H.-J. B\u00f6ckenhauer","year":"2008","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D.: Reoptimization of the metric deadline TSP. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol.\u00a05162, pp. 156\u2013167. Springer, Heidelberg (2008)"},{"key":"2_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-540-69903-3_24","volume-title":"Algorithm Theory \u2013 SWAT 2008","author":"D. Bil\u00f2","year":"2008","unstructured":"Bil\u00f2, D., B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., M\u00f6mke, T., Widmayer, P., Zych, A.: Reoptimization of steiner trees. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol.\u00a05124, pp. 258\u2013269. Springer, Heidelberg (2008)"},{"issue":"36","key":"2_CR10","doi-asserted-by":"publisher","first-page":"3428","DOI":"10.1016\/j.tcs.2008.04.039","volume":"410","author":"H.-J. B\u00f6ckenhauer","year":"2009","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. Theoretical Computer Science\u00a0410(36), 3428\u20133435 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"2_CR11","first-page":"86","volume":"4","author":"B. Escoffier","year":"2009","unstructured":"Escoffier, B., Milani\u010d, M., Paschos, V.T.: Simple and fast reoptimizations for the Steiner tree problem. Algorithmic Operations Research\u00a04(2), 86\u201394 (2009)","journal-title":"Algorithmic Operations Research"},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-13073-1_17","volume-title":"Algorithms and Complexity","author":"H.-J. B\u00f6ckenhauer","year":"2010","unstructured":"B\u00f6ckenhauer, H.-J., Freiermuth, K., Hromkovi\u010d, J., M\u00f6mke, T., Sprock, A., Steffen, B.: The Steiner tree problem with sharpened triangle inequality: hardness and reoptimization. In: Calamoneri, T., Diaz, J. (eds.) CIAC 2010. LNCS, vol.\u00a06078, pp. 180\u2013191. Springer, Heidelberg (2010)"},{"key":"2_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-642-02441-2_8","volume-title":"Combinatorial Pattern Matching","author":"D. Bil\u00f2","year":"2009","unstructured":"Bil\u00f2, D., B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., M\u00f6mke, T., Seibert, S., Zych, A.: Reoptimization of the shortest\u00a0common\u00a0superstring\u00a0problem. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009. LNCS, vol.\u00a05577, pp. 78\u201391. Springer, Heidelberg (2009)"},{"doi-asserted-by":"crossref","unstructured":"Bil\u00f2, D., B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., M\u00f6mke, T., Seibert, S., Zych, A.: Reoptimization of the shortest common superstring problem. Algorithmica (2010) (to appear)","key":"2_CR14","DOI":"10.1007\/978-3-642-02441-2_8"},{"unstructured":"Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the 0-1 knapsack problem. Technical Report 267, University of Brescia (2006)","key":"2_CR15"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-540-93980-1_16","volume-title":"Approximation and Online Algorithms","author":"D. Bil\u00f2","year":"2009","unstructured":"Bil\u00f2, D., Widmayer, P., Zych, A.: Reoptimization of weighted graph and covering problems. In: Bampis, E., Skutella, M. (eds.) WAOA 2008. LNCS, vol.\u00a05426, pp. 201\u2013213. Springer, Heidelberg (2009)"},{"key":"2_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-540-77566-9_5","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"H.-J. B\u00f6ckenhauer","year":"2008","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., M\u00f6mke, T., Widmayer, P.: On the hardness of reoptimization. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol.\u00a04910, pp. 50\u201365. Springer, Heidelberg (2008)"},{"issue":"1","key":"2_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C.H. Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Mathematics of Operations Research\u00a018(1), 1\u201311 (1993)","journal-title":"Mathematics of Operations Research"},{"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 (1976)","key":"2_CR19"},{"issue":"2","key":"2_CR20","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"},{"issue":"4","key":"2_CR21","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"},{"issue":"\/72","key":"2_CR22","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(\/72), 195\u2013207 (1971)","journal-title":"Networks"},{"key":"2_CR23","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1287\/opre.26.3.434","volume":"26","author":"C.H. Papadimitriou","year":"1978","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Some examples of difficult traveling salesman problems. Operations Research\u00a026, 434\u2013443 (1978)","journal-title":"Operations Research"}],"container-title":["Lecture Notes in Computer Science","Computation, Cooperation, and Life"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20000-7_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T22:53:37Z","timestamp":1560293617000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20000-7_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642199998","9783642200007"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20000-7_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}