{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:39Z","timestamp":1740109299584,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,1,27]],"date-time":"2020-01-27T00:00:00Z","timestamp":1580083200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,1,27]],"date-time":"2020-01-27T00:00:00Z","timestamp":1580083200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"DFG","award":["MO2889\/1-1","BL511\/10-1"],"award-info":[{"award-number":["MO2889\/1-1","BL511\/10-1"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In reoptimization, one is given an optimal solution to a problem instance and a (locally) modified instance. The goal is to obtain a solution for the modified instance. We aim to use information obtained from the given solution in order to obtain a better solution for the new instance than we are able to compute from scratch. In this paper, we consider Steiner tree reoptimization and address the optimality requirement of the provided solution. Instead of assuming that we are provided an optimal solution, we relax the assumption to the more realistic scenario where we are given an approximate solution with an upper bound on its performance guarantee. We show that for Steiner tree reoptimization there is a clear separation between local modifications where optimality is crucial for obtaining improved approximations and those instances where approximate solutions are acceptable starting points. For some of the local modifications that have been considered in previous research, we show that for every fixed <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varepsilon &gt; 0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, approximating the reoptimization problem with respect to a given <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1+\\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation is as hard as approximating the Steiner tree problem itself. In contrast, with a given optimal solution to the original problem it is known that one can obtain considerably improved results. Furthermore, we provide a new algorithmic technique that, with some further insights, allows us to obtain improved performance guarantees for Steiner tree reoptimization with respect to all remaining local modifications that have been considered in the literature: a required node of degree more than one becomes a Steiner node; a Steiner node becomes a required node; the cost of one edge is increased.<\/jats:p>","DOI":"10.1007\/s00453-020-00682-x","type":"journal-article","created":{"date-parts":[[2020,1,27]],"date-time":"2020-01-27T14:02:43Z","timestamp":1580133763000},"page":"1966-1988","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Robust Reoptimization of Steiner Trees"],"prefix":"10.1007","volume":"82","author":[{"given":"Keshav","family":"Goyal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2509-6972","authenticated-orcid":false,"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,27]]},"reference":[{"issue":"3","key":"682_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 42(3), 154\u2013159 (2003)","journal-title":"Networks"},{"issue":"17","key":"682_CR2","doi-asserted-by":"publisher","first-page":"1879","DOI":"10.1016\/j.dam.2010.08.003","volume":"158","author":"C Archetti","year":"2010","unstructured":"Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the 0\u20131 knapsack problem. Discrete Appl. Math. 158(17), 1879\u20131887 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"682_CR3","doi-asserted-by":"publisher","first-page":"1306","DOI":"10.1016\/j.cor.2012.12.010","volume":"40","author":"C Archetti","year":"2013","unstructured":"Archetti, C., Guastaroba, G., Speranza, M.G.: Reoptimizing the rural postman problem. Comput. Oper. Res. 40(5), 1306\u20131313 (2013)","journal-title":"Comput. Oper. Res."},{"key":"682_CR4","doi-asserted-by":"publisher","DOI":"10.1142\/9781848162778_0004","volume-title":"Complexity and Approximation in Reoptimization","author":"G Ausiello","year":"2011","unstructured":"Ausiello, G., Bonifaci, V., Escoffier, B.: Complexity and Approximation in Reoptimization. Imperial College Press\/World Scientific, London (2011)"},{"issue":"4","key":"682_CR5","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1016\/j.jda.2008.12.001","volume":"7","author":"G Ausiello","year":"2009","unstructured":"Ausiello, G., Escoffier, B., Monnot, J., Paschos, V.T.: Reoptimization of minimum and maximum traveling salesman\u2019s tours. J. Discrete Algorithms 7(4), 453\u2013463 (2009)","journal-title":"J. Discrete Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M., Fekete, S.P., Fineman, J.T., Gilbert, S.: Reallocation problems in scheduling. In: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u00a02013), pp. 271\u2013279. ACM (2013)","key":"682_CR6","DOI":"10.1145\/2486159.2486181"},{"doi-asserted-by":"crossref","unstructured":"Berg, T., Hempel, H.: Reoptimization of traveling salesperson problems: changing single edge-weights. In: Proceedings of the Third International Conference on Language and Automata Theory and Applications (LATA\u00a02009), LNCS, vol. 5457, pp. 141\u2013151. Springer (2009)","key":"682_CR7","DOI":"10.1007\/978-3-642-00982-2_12"},{"issue":"4","key":"682_CR8","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"MW Bern","year":"1989","unstructured":"Bern, M.W., Plassmann, P.E.: The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett. 32(4), 171\u2013176 (1989)","journal-title":"Inf. Process. Lett."},{"unstructured":"Bil\u00f2, D.: New algorithms for Steiner tree reoptimization. In: ICALP, LIPIcs, vol. 107, pp. 19:1\u201319:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)","key":"682_CR9"},{"issue":"2","key":"682_CR10","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s00453-010-9419-8","volume":"61","author":"D Bil\u00f2","year":"2011","unstructured":"Bil\u00f2, D., B\u00f6ckenhauer, H., Komm, D., Kr\u00e1lovic, R., M\u00f6mke, T., Seibert, S., Zych, A.: Reoptimization of the shortest common superstring problem. Algorithmica 61(2), 227\u2013251 (2011)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","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: Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT\u00a02008), LNCS, vol. 5124, pp. 258\u2013269 (2008)","key":"682_CR11","DOI":"10.1007\/978-3-540-69903-3_24"},{"doi-asserted-by":"crossref","unstructured":"Bil\u00f2, D., Widmayer, P., Zych, A.: Reoptimization of weighted graph and covering problems. In: Proceedings of the 6th International Workshop on Approximation and Online Algorithms (WAOA\u00a02008), Lecture Notes in Computer Science, vol. 5426, pp. 201\u2013213. Springer (2008)","key":"682_CR12","DOI":"10.1007\/978-3-540-93980-1_16"},{"unstructured":"Bil\u00f2, D., Zych, A.: New reoptimization techniques employed to Steiner tree problem. In: Proceedings of the 6th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS\u00a011) (2011)","key":"682_CR13"},{"doi-asserted-by":"crossref","unstructured":"Bil\u00f2, D., Zych, A.: New advances in reoptimizing the minimum Steiner tree problem. In: Mathematical Foundations of Computer Science 2012, pp. 184\u2013197. Springer (2012)","key":"682_CR14","DOI":"10.1007\/978-3-642-32589-2_19"},{"issue":"1","key":"682_CR15","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.jda.2009.04.001","volume":"8","author":"H B\u00f6ckenhauer","year":"2010","unstructured":"B\u00f6ckenhauer, H., Komm, D.: Reoptimization of the metric deadline TSP. J. Discrete Algorithms 8(1), 87\u2013100 (2010)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"682_CR16","first-page":"83","volume":"2","author":"HJ 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 Oper. Res. 2(2), 83\u201393 (2007)","journal-title":"Algorithmic Oper. Res."},{"key":"682_CR17","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.jda.2011.03.014","volume":"11","author":"HJ B\u00f6ckenhauer","year":"2012","unstructured":"B\u00f6ckenhauer, H.J., Freiermuth, K., Hromkovi\u010d, J., M\u00f6mke, T., Sprock, A., Steffen, B.: The Steiner tree reoptimization problem in graphs with sharpened triangle inequality. J. Discrete Algorithms 11, 73\u201386 (2012)","journal-title":"J. Discrete Algorithms"},{"issue":"36","key":"682_CR18","doi-asserted-by":"publisher","first-page":"3428","DOI":"10.1016\/j.tcs.2008.04.039","volume":"410","author":"HJ 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. Theor. Comput. Sci. 410(36), 3428\u20133435 (2009)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.J., Hromkovi\u010d, J., M\u00f6mke, T., Widmayer, P.: On the hardness of reoptimization. In: Proceedings of the 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM\u00a02008), LNCS, vol. 4910, pp. 50\u201365 (2008)","key":"682_CR19","DOI":"10.1007\/978-3-540-77566-9_5"},{"issue":"3","key":"682_CR20","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1137\/S0097539795281086","volume":"26","author":"A Borchers","year":"1997","unstructured":"Borchers, A., Du, D.Z.: The $$k$$-Steiner ratio in graphs. SIAM J. Comput. 26(3), 857\u2013869 (1997)","journal-title":"SIAM J. Comput."},{"key":"682_CR21","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2014.04.004","volume":"540","author":"N Boria","year":"2014","unstructured":"Boria, N., Della Croce, F.: Reoptimization in machine scheduling. Theor. Comput. Sci. 540, 13\u201326 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"682_CR22","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.tcs.2012.10.037","volume":"514","author":"N Boria","year":"2013","unstructured":"Boria, N., Monnot, J., Paschos, V.T.: Reoptimization of maximum weight induced hereditary subgraph problems. Theor. Comput. Sci. 514, 61\u201374 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"682_CR23","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1016\/j.jda.2009.07.002","volume":"8","author":"N Boria","year":"2010","unstructured":"Boria, N., Paschos, V.T.: Fast reoptimization for the minimum spanning tree problem. J. Discrete Algorithms 8(3), 296\u2013310 (2010)","journal-title":"J. Discrete Algorithms"},{"issue":"03","key":"682_CR24","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1051\/ro\/2011114","volume":"45","author":"N Boria","year":"2011","unstructured":"Boria, N., Paschos, V.T.: A survey on combinatorial optimization in dynamic environments. RAIRO-Oper. Res. 45(03), 241\u2013294 (2011)","journal-title":"RAIRO-Oper. Res."},{"issue":"1","key":"682_CR25","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/2432622.2432628","volume":"60","author":"J Byrka","year":"2013","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6 (2013)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Dai, W.: Reoptimization of minimum latency problem. In: COCOON, Lecture Notes in Computer Science, vol. 10392, pp. 162\u2013174. Springer (2017)","key":"682_CR26","DOI":"10.1007\/978-3-319-62389-4_14"},{"key":"682_CR27","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"SE Dreyfus","year":"1971","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1, 195\u2013207 (1971)","journal-title":"Networks"},{"issue":"2","key":"682_CR28","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 Oper. Res. 4(2), 86\u201394 (2009)","journal-title":"Algorithmic Oper. Res."},{"unstructured":"Hougardy, S., Silvanus, J., Vygen, J.: Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm. ArXiv preprint arXiv:1406.0492 (2014)","key":"682_CR29"},{"issue":"3","key":"682_CR30","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.ipl.2014.11.003","volume":"115","author":"J Monnot","year":"2015","unstructured":"Monnot, J.: A note on the traveling salesman reoptimization problem under vertex insertion. Inf. Process. Lett. 115(3), 435\u2013438 (2015)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"682_CR31","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(96)00042-X","volume":"72","author":"MW Sch\u00e4ffter","year":"1997","unstructured":"Sch\u00e4ffter, M.W.: Scheduling with forbidden sets. Discrete Appl. Math. 72(1), 155\u2013166 (1997)","journal-title":"Discrete Appl. Math."},{"unstructured":"Takahashi, H., Matsuyama, A.: An approximate solution for the Steiner problem in graphs. Math. Japonica 24(6), 573\u2013577 (1979\/1980)","key":"682_CR32"},{"unstructured":"Zych, A.: Reoptimization of NP-Hard Problems. Ph.D. Thesis, Dissertations, Eidgen\u00f6ssische Technische Hochschule ETH Z\u00fcrich, Nr. 20257, 2012 (2012)","key":"682_CR33"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00682-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00682-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00682-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,26]],"date-time":"2021-01-26T00:13:00Z","timestamp":1611619980000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00682-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,27]]},"references-count":33,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["682"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00682-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,1,27]]},"assertion":[{"value":"6 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}