{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T05:32:38Z","timestamp":1771651958491,"version":"3.50.1"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,1,27]],"date-time":"2017-01-27T00:00:00Z","timestamp":1485475200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00453-017-0274-8","type":"journal-article","created":{"date-parts":[[2017,1,27]],"date-time":"2017-01-27T19:43:06Z","timestamp":1485546186000},"page":"576-607","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["A Theory and Algorithms for Combinatorial Reoptimization"],"prefix":"10.1007","volume":"80","author":[{"given":"Baruch","family":"Schieber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hadas","family":"Shachnai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gal","family":"Tamir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tami","family":"Tamir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,1,27]]},"reference":[{"issue":"P3","key":"274_CR1","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1016\/j.tcs.2015.06.053","volume":"607","author":"FN Abu-Khzam","year":"2015","unstructured":"Abu-Khzam, F.N., Egan, J., Fellows, M.R., Rosamond, F.A., Shaw, P.: On the parameterized complexity of dynamic problems. Theor. Comput. Sci. 607(P3), 426\u2013434 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"274_CR2","unstructured":"Amato, G., Cattaneo, G., Italiano, G.F.: Experimental analysis of dynamic minimum spanning tree algorithms. In: Proceedings of 8th ACM-SIAM Symposium on Discrete Algorithms (SODA) (1997)"},{"key":"274_CR3","doi-asserted-by":"crossref","unstructured":"An, H.-C., Bhaskara, A., Chekuri, C., Gupta, S., Madan, V., Svensson, O.: Centrality of trees for capacitated $$k$$ k -center. In: Proceedings of IPCO, pp. 52\u201363 (2014)","DOI":"10.1007\/978-3-319-07557-0_5"},{"key":"274_CR4","doi-asserted-by":"crossref","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, 154\u2013159 (2003)","journal-title":"Networks"},{"issue":"17","key":"274_CR5","doi-asserted-by":"crossref","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 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"274_CR6","doi-asserted-by":"crossref","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"},{"key":"274_CR7","volume-title":"Computability in Context: Computation and Logic in the Real World","author":"G Ausiello","year":"2011","unstructured":"Ausiello, G., Bonifaci, V., Escoffier, B.: Complexity and approximation in reoptimization. In: Cooper, B., Sorbi, A. (eds.) Computability in Context: Computation and Logic in the Real World. Imperial College Press\/World Scientific, London (2011)"},{"issue":"4","key":"274_CR8","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1007\/BF01985757","volume":"1","author":"H Balakrishnan","year":"1995","unstructured":"Balakrishnan, H., Seshan, S., Katz, R.H.: Improving reliable transport and handoff performance in cellular wireless networks. Wirel. Netw. 1(4), 469\u2013481 (1995)","journal-title":"Wirel. Netw."},{"issue":"4","key":"274_CR9","first-page":"241","volume":"4","author":"G Baram","year":"2014","unstructured":"Baram, G., Tamir, T.: Reoptimization of the minimum total flow-time scheduling problem. Sustain. Comput. Inform. Syst. 4(4), 241\u2013251 (2014)","journal-title":"Sustain. Comput. Inform. Syst."},{"key":"274_CR10","doi-asserted-by":"crossref","unstructured":"Bender, M., Farach-Colton, M., Fekete, S., Fineman, J., Gilbert, S.: Reallocation problems in scheduling. In: Proceedings of 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 271\u2013279 (2013)","DOI":"10.1145\/2486159.2486181"},{"key":"274_CR11","doi-asserted-by":"crossref","unstructured":"Bender, M., Farach-Colton, M., Fekete, S., Fineman, J., Gilbert, S.: Cost-oblivious storage reallocation. In: Proceedings of 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pp. 278\u2013288 (2014)","DOI":"10.1145\/2594538.2594548"},{"issue":"3","key":"274_CR12","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/j.comnet.2005.03.004","volume":"50","author":"R Bhatia","year":"2006","unstructured":"Bhatia, R., Kodialam, M., Lakshman, T.V.: Fast network re-optimization schemes for MPLS and optical networks. Comput. Netw. 50(3), 317\u2013331 (2006)","journal-title":"Comput. Netw."},{"key":"274_CR13","doi-asserted-by":"crossref","unstructured":"Bilo, D., B\u00f6ckenhauer, H., Komm, D., Kr\u00e1lovi\u010d, R., M\u00f6mke, T., Seibert, S., Zych, A.: Reoptimization of the shortest common superstring problem. In: Proceedings of 20th Symposium on Combinatorial Pattern Matching (CPM) (2009)","DOI":"10.1007\/978-3-642-02441-2_8"},{"key":"274_CR14","doi-asserted-by":"crossref","unstructured":"Berger, A., Bonifaci, V., Grandoni, F., Sch\u00e4fer, G.: Budgeted matching and budgeted matroid intersection via the gasoline puzzle. In: Proceedings of IPCO, pp. 273\u2013287 (2008)","DOI":"10.1007\/978-3-540-68891-4_19"},{"issue":"2","key":"274_CR15","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":"274_CR16","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 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pp. 50\u201365 (2008)","DOI":"10.1007\/978-3-540-77566-9_5"},{"key":"274_CR17","unstructured":"Chou, C.F., Golubchik, L., Lui, J.C.S.: A performance study of dynamic replication techniques in continuous media servers. In: Proceedings of International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (IEEE MASCOTS), pp. 256\u2013264 (2000)"},{"key":"274_CR18","series-title":"Series in discrete mathematics and its applications","volume-title":"Handbook of Graph Theory, Chapter 10.2","author":"C Demetrescu","year":"2003","unstructured":"Demetrescu, C., Finocchi, I., Italiano, G.F.: Dynamic graph algorithms. In: Yellen, J., Gross, J.L. (eds.) Handbook of Graph Theory, Chapter 10.2. Series in discrete mathematics and its applications. CRC Press, Boca Raton (2003)"},{"key":"274_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, London (2013)"},{"key":"274_CR20","volume-title":"Facility Location: Applications and Theory","year":"2002","unstructured":"Drezner, Z., Hamacher, H. (eds.): Facility Location: Applications and Theory. Springer, New York (2002)"},{"key":"274_CR21","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0167-6377(85)90002-1","volume":"3","author":"ME Dyer","year":"1985","unstructured":"Dyer, M.E., Frieze, A.M.: A simple heuristic for the $$p$$ p -center problem. Oper. Res. Lett. 3, 285\u2013288 (1985)","journal-title":"Oper. Res. Lett."},{"key":"274_CR22","volume-title":"CRC Handbook of Algorithms and Theory of Computation, Chapter 8","author":"D Eppstein","year":"1999","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F.: Dynamic graph algorithms. In: Atallah, M.J. (ed.) CRC Handbook of Algorithms and Theory of Computation, Chapter 8. CRC Press, Boca Raton (1999)"},{"issue":"2","key":"274_CR23","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."},{"key":"274_CR24","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.H.: Optimal algorithms for approximate clustering. In: Proceedings of 20th Annual ACM Symposium on Theory of Computing (STOC) 434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"issue":"1","key":"274_CR25","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1287\/ijoc.1040.0081","volume":"18","author":"A Frangioni","year":"2006","unstructured":"Frangioni, A., Manca, A.: A computational study of cost reoptimization for min-cost flow problems. INFORMS J. Comput. 18(1), 61\u201370 (2006)","journal-title":"INFORMS J. Comput."},{"key":"274_CR26","volume-title":"Dynamic Routing in Telecommunication Networks","author":"A Gerald","year":"1997","unstructured":"Gerald, A.: Dynamic Routing in Telecommunication Networks. McGraw-Hill, New York (1997)"},{"key":"274_CR27","unstructured":"Golubchik, L., Khanna, S., Khuller, S., Thurimella, R., Zhu, A.: Approximation algorithms for data placement on parallel disks. In: Proceedings of 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 223\u2013232 (2000)"},{"key":"274_CR28","first-page":"263","volume":"17","author":"R Graham","year":"1969","unstructured":"Graham, R.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17, 263\u2013269 (1969)","journal-title":"SIAM J. Appl. Math."},{"issue":"1\u20132","key":"274_CR29","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/s10107-013-0703-7","volume":"146","author":"F Grandoni","year":"2014","unstructured":"Grandoni, F., Ravi, R., Singh, M., Zenklusen, R.: New approaches to multi-objective optimization. Math. Program. 146(1\u20132), 525\u2013554 (2014)","journal-title":"Math. Program."},{"key":"274_CR30","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"DS Hochbaum","year":"1995","unstructured":"Hochbaum, D.S.: Approximation Algorithms for NP-Hard Problems. PWS Publishing, Boston (1995)"},{"key":"274_CR31","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the $$k$$ k -center problem. Math. Oper. Res. 10, 180\u2013184 (1985)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"274_CR32","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"DS Hochbaum","year":"1986","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for bottleneck problems. J. ACM 33(3), 533\u2013550 (1986)","journal-title":"J. ACM"},{"key":"274_CR33","unstructured":"Hulu. http:\/\/www.hulu.com\/"},{"issue":"3","key":"274_CR34","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1145\/331499.331504","volume":"31","author":"AK Jain","year":"1999","unstructured":"Jain, A.K., Murty, M.N., Flynn, P.J.: Data clustering: a review. ACM Comput. Surv. 31(3), 264\u2013323 (1999)","journal-title":"ACM Comput. Surv."},{"key":"274_CR35","doi-asserted-by":"crossref","unstructured":"Karve, A., Kimbrel, T., Pacifici, G., Spreitzer, M., Steinder, M., Sviridenko, M., Tantawi, A.: Dynamic placement for clustered web applications. In: Proceedings of the 15th International Conference on World Wide Web (WWW \u201906), pp. 595\u2013604. ACM, New York, NY, USA (2006)","DOI":"10.1145\/1135777.1135865"},{"key":"274_CR36","unstructured":"Kashyap, S.: Algorithms for data placement, reconfiguration and monitoring in storage networks. Ph.D. Dissertation, Computer Science Department, Univ. of Maryland (2007)"},{"key":"274_CR37","doi-asserted-by":"crossref","unstructured":"Kashyap, S., Khuller, S., Wan, Y-C., Golubchik, L.: Fast reconfiguration of data placement in parallel disks. In: Proceedings of the Meeting on Algorithm Engineering & Experiments, pp. 95\u2013107. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA","DOI":"10.1137\/1.9781611972863.10"},{"key":"274_CR38","doi-asserted-by":"crossref","unstructured":"\u0141acki, J., O\u0107wieja, J., Pilipczuk, M., Sankowski, P., Zych, A.: The power of dynamic distance oracles: efficient dynamic algorithms for the Steiner tree. In: Proceedings of STOC (2015)","DOI":"10.1145\/2746539.2746615"},{"key":"274_CR39","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1287\/mnsc.16.1.77","volume":"16","author":"EL Lawler","year":"1969","unstructured":"Lawler, E.L., Moore, J.M.: A functional equation and its application to resource allocation and sequencing problems. Manag. Sci. 16, 77\u201384 (1969)","journal-title":"Manag. Sci."},{"key":"274_CR40","volume-title":"Communication Networks","author":"A Leon-Garcia","year":"2003","unstructured":"Leon-Garcia, A., Widjaja, I.: Communication Networks. McGraw-Hill, New York (2003)"},{"key":"274_CR41","unstructured":"Levin, M.S.: Restructuring in combinatorial optimization. arXiv:1102.1745 (2011)"},{"key":"274_CR42","unstructured":"Levin, M.S.: Towards integrated glance to restructuring in combinatorial optimization. arXiv:1512.06427 (2015)"},{"issue":"8","key":"274_CR43","doi-asserted-by":"crossref","first-page":"3633","DOI":"10.1137\/070698257","volume":"39","author":"G Lin","year":"2010","unstructured":"Lin, G., Nagarajan, C., Rajaraman, R., Williamson, D.P.: A general approach for incremental approximation and hierarchical clustering. SIAM J. Comput. 39(8), 3633\u20133669 (2010)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"274_CR44","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1287\/mnsc.15.1.102","volume":"15","author":"JM Moore","year":"1968","unstructured":"Moore, J.M.: An $$n$$ n -job, one machine sequencing algorithm for minimizing the number of late jobs. Manag. Sci. 15(1), 102\u2013109 (1968)","journal-title":"Manag. Sci."},{"key":"274_CR45","doi-asserted-by":"crossref","unstructured":"Nagarajan, V., Schieber, B., Shachnai, H.: The euclidean k-supplier problem. In: Proceedings of 16th International Conference on Integer Programming and Combinatorial Optimization (IPCO) (2013)","DOI":"10.1007\/978-3-642-36694-9_25"},{"key":"274_CR46","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/s00453-002-0988-z","volume":"35","author":"E Nardelli","year":"2003","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: Swapping a failing edge of a single source shortest paths tree is good and fast. Algorithmica 35, 56\u201374 (2003)","journal-title":"Algorithmica"},{"key":"274_CR47","volume-title":"A Textbook on ATM Telecommunications, Principles and Implementation","author":"PS Neelakanta","year":"2000","unstructured":"Neelakanta, P.S.: A Textbook on ATM Telecommunications, Principles and Implementation. CRC Press, Boca Raton (2000)"},{"key":"274_CR48","unstructured":"Netflix. http:\/\/www.netflix.com\/"},{"key":"274_CR49","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0167-6377(02)00192-X","volume":"31","author":"S Pallottino","year":"2003","unstructured":"Pallottino, S., Scutella, M.G.: A new algorithm for reoptimizing shortest paths when the arc costs change. Oper. Res. Lett. 31, 149\u2013160 (2003)","journal-title":"Oper. Res. Lett."},{"key":"274_CR50","doi-asserted-by":"crossref","unstructured":"Ravi, R., Goemans, M.X.: The constrained minimum spanning tree problem. In: Proceedings of 5th Workshop on Algorithm Theory, pp. 66\u201375 (1996)","DOI":"10.1007\/3-540-61422-2_121"},{"key":"274_CR51","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1007\/s004530010057","volume":"29","author":"H Shachnai","year":"2001","unstructured":"Shachnai, H., Tamir, T.: On two class-constrained versions of the multiple knapsack problem. Algorithmica 29, 442\u2013467 (2001)","journal-title":"Algorithmica"},{"key":"274_CR52","doi-asserted-by":"crossref","unstructured":"Shachnai, H., Tamir, G., Tamir, T.: Minimal cost reconfiguration of data placement in storage area network. In: Proceedings of 7rd Workshop on Approximation and Online Algorithms (WAOA) (2009)","DOI":"10.1007\/978-3-642-12450-1_21"},{"key":"274_CR53","doi-asserted-by":"crossref","unstructured":"Shachnai, H., Tamir, G., Tamir, T.: A theory and algorithms for combinatorial reoptimization. In: Proceedings of 10th Latin American Theoretical Informatics symposium (LATIN) (2012)","DOI":"10.1007\/978-3-642-29344-3_52"},{"issue":"15","key":"274_CR54","doi-asserted-by":"crossref","first-page":"2200","DOI":"10.1016\/j.dam.2005.04.013","volume":"154","author":"B Thiongane","year":"2006","unstructured":"Thiongane, B., Nagih, A., Plateau, G.: Lagrangian heuristics combined with reoptimization for the 0\u20131 bidimensional knapsack problem. Discrete Appl. Math. 154(15), 2200\u20132211 (2006)","journal-title":"Discrete Appl. Math."},{"key":"274_CR55","doi-asserted-by":"crossref","unstructured":"Thorup, M., Karger, D.R.: Dynamic graph algorithms with applications. In: Proceedings of 7th Scandinavian Workshop on Algorithm (SWAT) (2000)","DOI":"10.1007\/3-540-44985-X_1"},{"key":"274_CR56","unstructured":"Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of an FPTAS? In: Proceedings of 10th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 820\u2013829 (1999)"},{"key":"274_CR57","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1007\/s005300050067","volume":"5","author":"JL Wolf","year":"1997","unstructured":"Wolf, J.L., Yu, P.S., Shachnai, H.: Disk load balancing for video-on-demand systems. ACM Multimed. Syst. 5, 358\u2013370 (1997)","journal-title":"ACM Multimed. Syst."},{"key":"274_CR58","doi-asserted-by":"crossref","unstructured":"Yue, F., Tang, J.: A new approach for tree alignment based on local re-optimization. In: Proceedings on International Conference on BioMedical Engineering and Informatics (2008)","DOI":"10.1109\/BMEI.2008.290"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0274-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0274-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0274-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T01:48:49Z","timestamp":1568771329000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0274-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,27]]},"references-count":58,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["274"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0274-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1,27]]}}}