{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:05Z","timestamp":1781078165858,"version":"3.54.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,8,23]],"date-time":"2014-08-23T00:00:00Z","timestamp":1408752000000},"content-version":"tdm","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":[[2015,10]]},"DOI":"10.1007\/s00453-014-9930-4","type":"journal-article","created":{"date-parts":[[2014,8,22]],"date-time":"2014-08-22T14:28:20Z","timestamp":1408717700000},"page":"389-409","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Reallocation Problems in Scheduling"],"prefix":"10.1007","volume":"73","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Farach-Colton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S\u00e1ndor P.","family":"Fekete","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeremy T.","family":"Fineman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Gilbert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,8,23]]},"reference":[{"issue":"3","key":"9930_CR1","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(3), 154\u2013159 (2003)","journal-title":"Networks"},{"key":"9930_CR2","doi-asserted-by":"crossref","unstructured":"Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the 0\u20131 knapsack problem. Discrete Appl. Math. 158(17), 1879\u20131887 (Oct. 2010)","DOI":"10.1016\/j.dam.2010.08.003"},{"key":"9930_CR3","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1142\/9781848162778_0004","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, S.B., Sorbi, A. (eds.) Computability in Context: Computation and Logic in the Real World, pp. 101\u2013109. World Scientific, Singapore (2011)"},{"issue":"4","key":"9930_CR4","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"},{"issue":"5","key":"9930_CR5","doi-asserted-by":"crossref","first-page":"1370","DOI":"10.1137\/S009753970037446X","volume":"31","author":"B Awerbuch","year":"2002","unstructured":"Awerbuch, B., Azar, Y., Leonardi, S., Regev, O.: Minimizing the flow time without migration. SIAM J. Comput. 31(5), 1370\u20131382 (2002)","journal-title":"SIAM J. Comput."},{"key":"9930_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chan, H.-L., Khandekar, R., Pruhs, K., Stein, C., Schieber, B.: Non-preemptive min-sum scheduling with resource augmentation. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 614\u2013624 (2007)","DOI":"10.1109\/FOCS.2007.11"},{"issue":"1","key":"9930_CR7","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/j.jcss.2003.06.001","volume":"68","author":"L Becchetti","year":"2004","unstructured":"Becchetti, L., Leonardi, S., Muthukrishnan, S.: Average stretch without migration. J. Comput. Syst. Sci. 68(1), 80\u201395 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"9930_CR8","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), pp. 271\u2013279 (2013)","DOI":"10.1145\/2486159.2486181"},{"key":"9930_CR9","doi-asserted-by":"crossref","unstructured":"Bender, M. A., Farach-Colton, M., Fekete, S. P., Fineman, J. T., Gilbert S.: Cost-oblivious storage reallocation. In: Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) (2014)","DOI":"10.1145\/2594538.2594548"},{"key":"9930_CR10","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Fineman, J.T., Gilbert S.: A new approach to incremental topological ordering. In: Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1108\u20131115, January (2009)","DOI":"10.1137\/1.9781611973068.120"},{"key":"9930_CR11","first-page":"32","volume":"4","author":"MA Bender","year":"2007","unstructured":"Bender, M.A., Hu, H.: An adaptive packed-memory array. Trans. Database Syst. 4, 32 (2007)","journal-title":"Trans. Database Syst."},{"issue":"3","key":"9930_CR12","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/2362389.2362392","volume":"34","author":"A Bendersky","year":"2012","unstructured":"Bendersky, A., Petrank, E.: Space overhead bounds for dynamic memory management with partial compaction. ACM Trans. Program. Lang. Syst. 34(3), 13 (2012)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"3","key":"9930_CR13","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0166-218X(85)90046-0","volume":"10","author":"J B\u0142a\u017cewicz","year":"1985","unstructured":"B\u0142a\u017cewicz, J., Nawrocki, J.: Dynamic storage allocation with limited compaction\u2014complexity and some practical implications. Discrete Appl. Math. 10(3), 241\u2013253 (1985)","journal-title":"Discrete Appl. Math."},{"key":"9930_CR14","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Forlizzi, L., Hromkovic, J., Kneis, J., Kupke, J., Proietti, G., Widmayer P.: Reusing optimal TSP solutions for locally modified input instances. In: Proceedings of the 4th IFIP International Conference on Theoretical Computer Science (TCS), pp. 251\u2013270 (2006)","DOI":"10.1007\/978-0-387-34735-6_21"},{"key":"9930_CR15","unstructured":"Caprara, A., Galli, L., Kroon, L., Mar\u00f3ti, G., Toth P.: Robust train routing and online re-scheduling. In: Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), vol. 14, pp. 24\u201333 (2010)"},{"key":"9930_CR16","unstructured":"Chiraphadhanakul V., Barnhart C.: Robust flight schedules through slack re-allocation. Submitted (2011)"},{"key":"9930_CR17","doi-asserted-by":"crossref","unstructured":"Cohen N., Petrank E.: Limitations of partial compaction: towards practical bounds. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pp. 309\u2013320 (2013)","DOI":"10.1145\/2491956.2491973"},{"key":"9930_CR18","doi-asserted-by":"crossref","unstructured":"Davis, S., Edmonds, J., Impagliazzo R.: Online algorithms to minimize resource reallocations and network communication. In APPROX-RANDOM, pp. 104\u2013115 (2006)","DOI":"10.1007\/11830924_12"},{"key":"9930_CR19","doi-asserted-by":"crossref","unstructured":"Fekete, S.P., Kamphans, T., Schweer, N., Tessars, C., van der Veen, J.C., Angermeier, J., Koch, D., Teich, J.: Dynamic defragmentation of reconfigurable devices. ACM Trans. Reconfigurable Technol. Syst. 5(2), 8:1\u20138:20 (June 2012)","DOI":"10.1145\/2209285.2209287"},{"key":"9930_CR20","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Kavitha, T., Mathew, R., Sen, S., Tarjan R.E.: Faster algorithms for incremental topological ordering. In: Proceedings of the 35th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 421\u2013433, July (2008)","DOI":"10.1007\/978-3-540-70575-8_35"},{"key":"9930_CR21","doi-asserted-by":"crossref","unstructured":"Hall N.G., Potts C.N.: Rescheduling for new orders. Oper. Res. 52(3), 440\u2013453 (2004)","DOI":"10.1287\/opre.1030.0101"},{"key":"9930_CR22","doi-asserted-by":"crossref","unstructured":"Itai, A., Konheim, A.G., Rodeh M.: A sparse table implementation of priority queues. In: Proceedings of the 8th Internationl Colloquium on Automata, Languages, and Programming (ICALP), vol. 115 of Lecture Notes in Computer Science, pp. 417\u2013431 (1981)","DOI":"10.1007\/3-540-10843-2_34"},{"key":"9930_CR23","unstructured":"Jackson J.: Scheduling a production line to minimize maximum tardiness. Technical Report, Management Science Research Project Research Report 43, University of California, Los Angeles (1955)"},{"key":"9930_CR24","doi-asserted-by":"crossref","unstructured":"Jansen K., Klein K.-M.: A robust afptas for online bin packing with polynomial migration, In: Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 589\u2013600 (2013)","DOI":"10.1007\/978-3-642-39206-1_50"},{"issue":"3","key":"9930_CR25","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1287\/trsc.1090.0269","volume":"43","author":"H Jiang","year":"2009","unstructured":"Jiang, H., Barnhart, C.: Dynamic airline scheduling. Transp. Sci. 43(3), 336\u2013354 (2009)","journal-title":"Transp. Sci."},{"key":"9930_CR26","first-page":"214","volume":"47","author":"B Kalyanasundaram","year":"1995","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47, 214\u2013221 (1995)","journal-title":"J. ACM"},{"key":"9930_CR27","unstructured":"Katriel I., Bodlaender H.L.: Online topological ordering. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 443\u2013450, January (2005)"},{"key":"9930_CR28","volume-title":"The Art of Computer Programming: Fundamental Algorithms, vol. 1","author":"DE Knuth","year":"1997","unstructured":"Knuth, D.E.: The Art of Computer Programming: Fundamental Algorithms, vol. 1, 3rd edn. Addison-Wesley, New York (1997)","edition":"3"},{"key":"9930_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2620-6","volume-title":"Robust Discrete Optimization and Its Applications","author":"p Kouvelis","year":"1997","unstructured":"Kouvelis, p, Yu, G.: Robust Discrete Optimization and Its Applications. Kluwer, Amsterdam (1997)"},{"issue":"1","key":"9930_CR30","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1287\/trsc.1050.0134","volume":"40","author":"S Lan","year":"2006","unstructured":"Lan, S., Clarke, J.-P., Barnhart, C.: Planning for robust airline operations: Optimizing aircraft routings and flight departure times to minimize passenger disruptions. Transp. Sci. 40(1), 15\u201328 (2006)","journal-title":"Transp. Sci."},{"key":"9930_CR31","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1137\/S089548019325647X","volume":"9","author":"MG Luby","year":"1996","unstructured":"Luby, M.G., Naor, J., Orda, A.: Tight bounds for dynamic storage allocation. SIAM J. Discret. Math. 9, 155\u2013166 (1996)","journal-title":"SIAM J. Discret. Math."},{"key":"9930_CR32","doi-asserted-by":"crossref","unstructured":"Mulvey, J.M., Vanderbei, R.J., Zenios S.A.: Robust optimization of large-scale systems. Oper. Res. 43(2), 264\u2013281 (1995)","DOI":"10.1287\/opre.43.2.264"},{"issue":"2","key":"9930_CR33","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/s00453-001-0068-9","volume":"32","author":"CA Phillips","year":"2002","unstructured":"Phillips, C.A., Stein, C., Torng, E., Wein, J.: Optimal time-critical scheduling via resource augmentation. Algorithmica 32(2), 163\u2013200 (2002)","journal-title":"Algorithmica"},{"key":"9930_CR34","doi-asserted-by":"crossref","unstructured":"Robson, J.M.: An estimate of the store size necessary for dynamic storage allocation. J. ACM 18(3), 416\u2013423 (July 1971)","DOI":"10.1145\/321650.321658"},{"issue":"2","key":"9930_CR35","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1287\/moor.1090.0381","volume":"34","author":"P Sanders","year":"2009","unstructured":"Sanders, P., Sivadasan, N., Skutella, M.: Online scheduling with bounded migration. Math. Oper. Res. 34(2), 481\u2013498 (2009)","journal-title":"Math. Oper. Res."},{"key":"9930_CR36","doi-asserted-by":"crossref","unstructured":"Shachnai, H., Tamir, G., Tamir T.: A theory and algorithms for combinatorial reoptimization. In: Proceedings of the 10th Latin American Theoretical INformatics Symposium (LATIN), pp. 618\u2013630 (2012)","DOI":"10.1007\/978-3-642-29344-3_52"},{"key":"9930_CR37","doi-asserted-by":"crossref","unstructured":"Ting D.W.: Allocation and compaction\u2014a mathematical model for memory management. In: Proceedings of the ACM SIGMETRICS Conference on Computer Performance Modeling Measurement and Evaluation (SIGMETRICS), pp. 311\u2013317 (1976)","DOI":"10.1145\/800200.806206"},{"key":"9930_CR38","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1002\/nav.3800330414","volume":"33","author":"CA Tovey","year":"1986","unstructured":"Tovey, C.A.: Rescheduling to minimize makespan on a changing number of identical processors. Naval Res. Logist. 33, 717\u2013724 (1986)","journal-title":"Naval Res. Logist."},{"key":"9930_CR39","doi-asserted-by":"crossref","unstructured":"Unal, A.T., Uzsoy, R., Kiran A.S.: Rescheduling on a single machine with part-type dependent setup times and deadlines. Ann. Oper. Res. 70, 93\u2013113 (1997)","DOI":"10.1023\/A:1018955111939"},{"key":"9930_CR40","unstructured":"Verschae J.C.: The Power of Recourse in Online Optimization Robust Solutions for Scheduling, Matroid and MST Problems The Power of Recourse in Online Optimization: Robust Solutions for Scheduling, Matroid and MST Problems. PhD thesis, Technischen Universit\u00e4t Berlin, June (2012)"},{"issue":"1","key":"9930_CR41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.2000.1074","volume":"35","author":"J Westbrook","year":"2000","unstructured":"Westbrook, J.: Load balancing for response time. J. Algorithms 35(1), 1\u201316 (2000)","journal-title":"J. Algorithms"},{"key":"9930_CR42","doi-asserted-by":"crossref","unstructured":"Willard D.: Maintaining dense sequential files in a dynamic environment (extended abstract). In: Proceedings of the 14th Annual Symposium on Theory of Computing (STOC), pp. 114\u2013121 (1982)","DOI":"10.1145\/800070.802183"},{"key":"9930_CR43","doi-asserted-by":"crossref","unstructured":"Willard D.E.: Good worst-case algorithms for inserting and deleting records in dense sequential files. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 251\u2013260 (1986)","DOI":"10.1145\/16894.16879"},{"issue":"2","key":"9930_CR44","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0890-5401(92)90034-D","volume":"97","author":"DE Willard","year":"1992","unstructured":"Willard, D.E.: A density control algorithm for doing insertions and deletions in a sequentially ordered file in good worst-case time. Inf. Comput. 97(2), 150\u2013204 (1992)","journal-title":"Inf. Comput."},{"issue":"3","key":"9930_CR45","doi-asserted-by":"crossref","first-page":"240","DOI":"10.2307\/2319522","volume":"81","author":"D Woodall","year":"1974","unstructured":"Woodall, D.: The bay restaurant-a linear storage problem. Am. Math. Monthly 81(3), 240\u2013246 (1974)","journal-title":"Am. Math. Monthly"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9930-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9930-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9930-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T06:03:39Z","timestamp":1565762619000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9930-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,23]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["9930"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9930-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,23]]}}}