{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T11:10:30Z","timestamp":1725707430556},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642348617"},{"type":"electronic","value":"9783642348624"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34862-4_4","type":"book-chapter","created":{"date-parts":[[2012,11,26]],"date-time":"2012-11-26T09:00:11Z","timestamp":1353920411000},"page":"52-66","source":"Crossref","is-referenced-by-count":1,"title":["Reoptimization of the Minimum Total Flow-Time Scheduling Problem"],"prefix":"10.1007","author":[{"given":"Guy","family":"Baram","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tami","family":"Tamir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"Amato, G., Cattaneo, G., Italiano, G.F.: Experimental analysis of dynamic minimum spanning tree algorithms. In: Proc. of 8th SODA (1997)"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the 0-1 knapsack problem. Discrete Applied Mathematics\u00a0158(17) (2010)","DOI":"10.1016\/j.dam.2010.08.003"},{"key":"4_CR3","doi-asserted-by":"crossref","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 (2011)","DOI":"10.1142\/9781848162778_0004"},{"issue":"4","key":"4_CR4","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 salesmans tours. J. of Discrete Algorithms\u00a07(4), 453\u2013463 (2009)","journal-title":"J. of Discrete Algorithms"},{"key":"4_CR5","unstructured":"Baram, G., Tamir, T.: Reoptimization of the minimum total flow-time scheduling problem (full version), \n                  \n                    http:\/\/www.faculty.idc.ac.il\/tami\/Papers\/BTfull.pdf"},{"key":"4_CR6","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) (2007)"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"J.L. Bruno","year":"1974","unstructured":"Bruno, J.L., Coffman, E.G., Sethi, R.: Scheduling independent tasks to reduce mean finishing time. Communications of the ACM\u00a017, 382\u2013387 (1974)","journal-title":"Communications of the ACM"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0167-6377(82)90006-2","volume":"1","author":"R. Chandrasekaran","year":"1982","unstructured":"Chandrasekaran, R., Kaboadi, S.N., Murty, K.G.: Some NP-complete problems in linear programming. Operations Research Letters\u00a01, 101\u2013104 (1982)","journal-title":"Operations Research Letters"},{"key":"4_CR9","unstructured":"Conway, R.W., Maxwell, W.L., Miller, L.W.: Theory of Scheduling. AddisonWesley (1967)"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F.: Dynamic graph algorithms. In: Atallah, M.J. (ed.) CRC Handbook of Algorithms and Theory of Computation, ch. 8 (1999)","DOI":"10.1201\/9781420049503-c9"},{"key":"4_CR11","unstructured":"Escoffier, B., Milani\u010d, M., Paschos, V.T: Simple and fast reoptimizations for the Steiner tree problem. DIMACS Technical Report 2007-01"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R.L. Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Math.\u00a05, 287\u2013326 (1979)","journal-title":"Annals of Discrete Math."},{"key":"4_CR13","unstructured":"Grandoni, F., Zenklusen, R.: Optimization with more than one budget. In: Proc. of ESA (2010)"},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1287\/opre.21.3.846","volume":"21","author":"W. Horn","year":"1973","unstructured":"Horn, W.: Minimizing average flow-time with parallel machines. Operations Research\u00a021, 846\u2013847 (1973)","journal-title":"Operations Research"},{"key":"4_CR15","first-page":"7","volume":"1","author":"A.V. Karzanov","year":"1987","unstructured":"Karzanov, A.V.: Maximum matching of given weight in complete and complete bipartite graphs. Kibernetika\u00a01, 7\u201311 (1987); English translation in CYBNAW 23, 8\u201313","journal-title":"Kibernetika"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Mattox, D.: Handbook of Physical Vapor Deposition (PVD) Processing, 2nd edn. Elsevier (2010)","DOI":"10.1016\/B978-0-8155-2037-5.00008-3"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: Swapping a failing edge of a single source shortest paths tree is good and fast. Algorithmica\u00a035 (2003)","DOI":"10.1007\/s00453-002-0988-z"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Pallottino, S., Scutella, M.G.: A new algorithm for reoptimizing shortest paths when the arc costs change. Operations Research Letters\u00a031 (2003)","DOI":"10.1016\/S0167-6377(02)00192-X"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/3-540-61422-2_121","volume-title":"Algorithm Theory - SWAT \u201996","author":"R. Ravi","year":"1996","unstructured":"Ravi, R., Goemans, M.X.: The Constrained Minimum Spanning Tree Problem. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 66\u201375. Springer, Heidelberg (1996)"},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-642-12450-1_21","volume-title":"Approximation and Online Algorithms","author":"H. Shachnai","year":"2010","unstructured":"Shachnai, H., Tamir, G., Tamir, T.: Minimal Cost Reconfiguration of Data Placement in Storage Area Network. In: Bampis, E., Jansen, K. (eds.) WAOA 2009. LNCS, vol.\u00a05893, pp. 229\u2013241. Springer, Heidelberg (2010)"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1007\/978-3-642-29344-3_52","volume-title":"LATIN 2012: Theoretical Informatics","author":"H. Shachnai","year":"2012","unstructured":"Shachnai, H., Tamir, G., Tamir, T.: A Theory and Algorithms for Combinatorial Reoptimization. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol.\u00a07256, pp. 618\u2013630. Springer, Heidelberg (2012)"},{"key":"4_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/3-540-45535-3_31","volume-title":"Integer Programming and Combinatorial Optimization","author":"R.A. Sitters","year":"2001","unstructured":"Sitters, R.A.: Two NP-Hardness Results for Preemptive Minsum Scheduling of Unrelated Parallel Machines. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, pp. 396\u2013405. Springer, Heidelberg (2001)"},{"key":"4_CR23","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W.E. Smith","year":"1956","unstructured":"Smith, W.E.: Various optimizers for single-stage production. Naval Research Logistics Quarterly\u00a03, 59\u201366 (1956)","journal-title":"Naval Research Logistics Quarterly"},{"key":"4_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44985-X_1","volume-title":"Algorithm Theory - SWAT 2000","author":"M. Thorup","year":"2000","unstructured":"Thorup, M., Karger, D.R.: Dynamic Graph Algorithms with Applications. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 1\u20139. Springer, Heidelberg (2000)"},{"key":"4_CR25","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0166-218X(01)00300-6","volume":"121","author":"T. Yi","year":"2002","unstructured":"Yi, T., Murty, K.G., Spera, C.: Matchings in colored bipartite networks. Discrete Applied Mathematics\u00a0121, 261\u2013277 (2002)","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Design and Analysis of Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34862-4_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T13:06:49Z","timestamp":1620133609000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34862-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642348617","9783642348624"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34862-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}