{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:07Z","timestamp":1725558967340},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_29","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"336-347","source":"Crossref","is-referenced-by-count":1,"title":["Max-min Online Allocations with a Reordering Buffer"],"prefix":"10.1007","author":[{"given":"Leah","family":"Epstein","sequence":"first","affiliation":[]},{"given":"Asaf","family":"Levin","sequence":"additional","affiliation":[]},{"given":"Rob","family":"van Stee","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"29_CR1","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1137\/S0097539797324874","volume":"29","author":"S. Albers","year":"1999","unstructured":"Albers, S.: Better bounds for online scheduling. SIAM Journal on Computing\u00a029(2), 459\u2013473 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Saberi, A.: An approximation algorithm for max-min fair allocation of indivisible goods. In: Proc. 39th Symp. Theory of Computing (STOC), pp. 114\u2013121 (2007)","DOI":"10.1145\/1250790.1250808"},{"issue":"3","key":"29_CR3","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J. Aspnes","year":"1997","unstructured":"Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O.: On-line load balancing with applications to machine scheduling and virtual circuit routing. Journal of the ACM\u00a044(3), 486\u2013504 (1997)","journal-title":"Journal of the ACM"},{"key":"29_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/3-540-63397-9_3","volume-title":"Algorithms - ESA 1997","author":"Y. Azar","year":"1997","unstructured":"Azar, Y., Epstein, L.: On-line machine covering. In: Burkard, R.E., Woeginger, G.J. (eds.) ESA 1997. LNCS, vol.\u00a01284, pp. 23\u201336. Springer, Heidelberg (1997)"},{"issue":"2","key":"29_CR5","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1006\/jagm.1995.1008","volume":"18","author":"Y. Azar","year":"1995","unstructured":"Azar, Y., Naor, J., Rom, R.: The competitiveness of on-line assignments. Journal of Algorithms\u00a018(2), 221\u2013237 (1995)","journal-title":"Journal of Algorithms"},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Sviridenko, M.: The Santa Claus problem. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 31\u201340 (2006)","DOI":"10.1145\/1132516.1132522"},{"key":"29_CR7","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1006\/jagm.1999.1070","volume":"35","author":"P. Berman","year":"2000","unstructured":"Berman, P., Charikar, M., Karpinski, M.: On-line load balancing for related machines. Journal of Algorithms\u00a035, 108\u2013121 (2000)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"29_CR8","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1142\/S0217595907001255","volume":"24","author":"S.-Y. Cai","year":"2007","unstructured":"Cai, S.-Y.: Semi-online machine covering. Asia-Pacific J. of Oper. Res.\u00a024(3), 373\u2013382 (2007)","journal-title":"Asia-Pacific J. of Oper. Res."},{"issue":"4","key":"29_CR9","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s10878-007-9078-0","volume":"15","author":"O. Chassid","year":"2008","unstructured":"Chassid, O., Epstein, L.: The hierarchical model for load balancing on two machines. Journal of Combinatorial Optimization\u00a015(4), 305\u2013314 (2008)","journal-title":"Journal of Combinatorial Optimization"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0167-6377(95)00039-9","volume":"18","author":"B. Chen","year":"1995","unstructured":"Chen, B., van Vliet, A., Woeginger, G.J.: An optimal algorithm for preemptive on-line scheduling. Operations Research Letters\u00a018, 127\u2013131 (1995)","journal-title":"Operations Research Letters"},{"key":"29_CR11","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0167-6377(92)90004-M","volume":"11","author":"J. Csirik","year":"1992","unstructured":"Csirik, J., Kellerer, H., Woeginger, G.: The exact LPT-bound for maximizing the minimum completion time. Operations Research Letters\u00a011, 281\u2013287 (1992)","journal-title":"Operations Research Letters"},{"issue":"2","key":"29_CR12","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1137\/0603019","volume":"3","author":"B.L. Deuermeyer","year":"1982","unstructured":"Deuermeyer, B.L., Friesen, D.K., Langston, M.A.: Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIAM Journal on Discrete Mathematics\u00a03(2), 190\u2013196 (1982)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"29_CR13","doi-asserted-by":"crossref","unstructured":"D\u00f3sa, G., Epstein, L.: Online scheduling with a buffer on related machines. Journal of Combinatorial Optimization. (to appear), doi:10.1007\/s10878-008-9200-y","DOI":"10.1007\/s10878-008-9200-y"},{"key":"29_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1007\/978-3-642-04128-0_41","volume-title":"Algorithms - ESA 2009","author":"G. D\u00f3sa","year":"2009","unstructured":"D\u00f3sa, G., Epstein, L.: Preemptive online scheduling with reordering. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 456\u2013467. Springer, Heidelberg (2009)"},{"key":"29_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/11671411_9","volume-title":"Approximation and Online Algorithms","author":"T. Ebenlendr","year":"2006","unstructured":"Ebenlendr, T., Noga, J., Sgall, J., Woeginger, G.J.: A note on semi-online machine covering. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol.\u00a03879, pp. 110\u2013118. Springer, Heidelberg (2006)"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Englert, M., \u00d6zmen, D., Westermann, M.: The power of reordering for online minimum makespan scheduling. In: Proc. 48th Symp. Foundations of Computer Science (FOCS), pp. 603\u2013612 (2008)","DOI":"10.1109\/FOCS.2008.46"},{"issue":"1","key":"29_CR17","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00453-003-1077-7","volume":"39","author":"L. Epstein","year":"2004","unstructured":"Epstein, L., Sgall, J.: Approximation schemes for scheduling on uniformly related and identical parallel machines. Algorithmica\u00a039(1), 43\u201357 (2004)","journal-title":"Algorithmica"},{"issue":"1","key":"29_CR18","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1287\/moor.6.1.74","volume":"6","author":"D.K. Friesen","year":"1981","unstructured":"Friesen, D.K., Deuermeyer, B.L.: Analysis of greedy solutions for a replacement part sequencing problem. Mathematics of Operations Reasearch\u00a06(1), 74\u201387 (1981)","journal-title":"Mathematics of Operations Reasearch"},{"key":"29_CR19","unstructured":"Gormley, T., Reingold, N., Torng, E., Westbrook, J.: Generating adversaries for request-answer games. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 564\u2013565 (2000)"},{"key":"29_CR20","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R.L. Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Sys. Tech. J.\u00a045, 1563\u20131581 (1966)","journal-title":"Bell Sys. Tech. J."},{"issue":"4","key":"29_CR21","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s10878-005-4923-5","volume":"10","author":"Y. Jiang","year":"2005","unstructured":"Jiang, Y., Tan, Z., He, Y.: Preemptive machine covering on parallel machines. Journal of Combinatorial Optimization\u00a010(4), 345\u2013363 (2005)","journal-title":"Journal of Combinatorial Optimization"},{"key":"29_CR22","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/S0167-6377(98)00005-4","volume":"21","author":"H. Kellerer","year":"1997","unstructured":"Kellerer, H., Kotov, V., Speranza, M.G., Tuza, Z.: Semi online algorithms for the partition problem. Operations Research Letters\u00a021, 235\u2013242 (1997)","journal-title":"Operations Research Letters"},{"issue":"1","key":"29_CR23","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.tcs.2006.11.015","volume":"372","author":"Z. Tan","year":"2007","unstructured":"Tan, Z., Wu, Y.: Optimal semi-online algorithms for machine covering. Theoretical Computer Science\u00a0372(1), 69\u201380 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"29_CR24","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0167-6377(96)00055-7","volume":"20","author":"G.J. Woeginger","year":"1997","unstructured":"Woeginger, G.J.: A polynomial time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters\u00a020(4), 149\u2013154 (1997)","journal-title":"Operations Research Letters"},{"key":"29_CR25","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/S0020-0190(97)00006-9","volume":"61","author":"G. Zhang","year":"1997","unstructured":"Zhang, G.: A simple semi on-line algorithm for P2\/\/C\n                   max  with a buffer. Information Processing Letters\u00a061, 145\u2013148 (1997)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T19:40:54Z","timestamp":1558294854000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}