{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T11:06:29Z","timestamp":1751367989083,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540651420"},{"type":"electronic","value":"9783540495437"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49543-6_7","type":"book-chapter","created":{"date-parts":[[2007,6,7]],"date-time":"2007-06-07T02:58:05Z","timestamp":1181185085000},"page":"71-81","source":"Crossref","is-referenced-by-count":12,"title":["On-line Bin-Stretching"],"prefix":"10.1007","author":[{"given":"Yossi","family":"Azar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oded","family":"Regev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,6,11]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"S. Albers. Better bounds for on-line scheduling. In Proc. 29th ACM Symp. on Theory of Computing, pages 130\u2013139, 1997.","DOI":"10.1145\/258533.258566"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts. On-line load balancing with applications to machine scheduling and virtual circuit routing. In Proc. 25th ACM Symposium on the Theory of Computing, pages 623\u2013631, 1993. Also in Journal of the ACM 44:3 (1997) pp. 486\u2013504.","DOI":"10.1145\/258128.258201"},{"key":"7_CR3","unstructured":"B. Awerbuch, Y. Azar, S. Plotkin, and O. Waarts. Competitive routing of virtual circuits with unknown duration. In Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, pages 321\u2013327, 1994."},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Y. Azar, A. Broder, and A. Karlin. On-line load balancing. In Proc. 33rd IEEE Symposium on Foundations of Computer Science, pages 218\u2013225, 1992. Also in Theoretical Compute Science 130 (1994) pp. 73\u201384.","DOI":"10.1016\/0304-3975(94)90153-8"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Y. Azar and L. Epstein. On-line load balancing of temporary tasks on identical machines. In 5th Israeli Symp. on Theory of Computing and Systems, pages 119\u2013125, 1997.","DOI":"10.1109\/ISTCS.1997.595163"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Y. Azar, B. Kalyanasundaram, S. Plotkin, K. Pruhs, and O. Waarts. Online load balancing of temporary tasks. In Proc. Workshop on Algorithms and Data Structures, pages 119\u2013130, August 1993.","DOI":"10.1007\/3-540-57155-8_241"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Y. Bartal, A. Fiat, H. Karloff, and R. Vohra. New algorithms for an ancient scheduling problem. In Proc. 24th ACM Symposium on Theory of Algorithms, pages 51\u201358, 1992. To appear in Journal of Computer and System Sciences.","DOI":"10.1145\/129712.129718"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0020-0190(94)00110-3","volume":"51","author":"B. Chen","year":"1994","unstructured":"B. Chen, A. van Vliet, and G. Woeginger. A lower bound for randomized on-line scheduling algorithms. Information Processing Letters, 51:219\u2013222, 1994.","journal-title":"Information Processing Letters"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0167-6377(94)90071-X","volume":"16","author":"B. Chen","year":"1994","unstructured":"B. Chen, A. van Vliet, and G. J. Woeginger. New lower and upper bounds for on-line scheduling. Operations Research Letters, 16:221\u2013230, 1994.","journal-title":"Operations Research Letters"},{"key":"7_CR10","unstructured":"E. G. Coffman, M. R. Garey, and D. S. Johnson. Approximation algorithms for bin packing: a survey. In D. Hochbaum, editor, Approximation algorithms. 1996."},{"key":"7_CR11","first-page":"107","volume":"9","author":"U. Faigle","year":"1989","unstructured":"U. Faigle, W. Kern, and G. Turan. On the performance of online algorithms for partition problems. Acta Cybernetica, 9:107\u2013119, 1989.","journal-title":"Acta Cybernetica"},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/0222026","volume":"22","author":"G. Galambos","year":"1993","unstructured":"G. Galambos and G. J. Woeginger. An on-line scheduling heuristic with better worst case ratio than graham\u2019s list scheduling. SIAM J. Computing, 22:349\u2013355, 1993.","journal-title":"SIAM J. Computing"},{"key":"7_CR13","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability. W.H. Freeman and Company, San Francisco, 1979."},{"key":"7_CR14","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":"R.L. Graham. Bounds for certain multiprocessor anomalies. Bell System Technical Journal, 45:1563\u20131581, 1966.","journal-title":"Bell System Technical Journal"},{"key":"7_CR15","first-page":"263","volume":"17","author":"R.L. Graham","year":"1969","unstructured":"R.L. Graham. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math, 17:263\u2013269, 1969.","journal-title":"SIAM J. Appl. Math"},{"issue":"3","key":"7_CR16","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"D. Hochbaum","year":"1988","unstructured":"D. Hochbaum and D. Shmoys. A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM Journal on Computing, 17(3):539\u2013551, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"7_CR17","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D. S. Hochbaum","year":"1987","unstructured":"D. S. Hochbaum and D. B. Shmoys. Using dual approximation algorithms for scheduling problems: Theoretical and practical results. J. of the ACM, 34(1):144\u2013162, January 1987.","journal-title":"J. of the ACM"},{"key":"7_CR18","volume-title":"PhD thesis","author":"D. S. Johnson","year":"1973","unstructured":"D. S. Johnson. Near-optimal bin packing algorithms. PhD thesis, MIT, Cambridge, MA, 1973."},{"key":"7_CR19","unstructured":"D. R. Karger, S. J. Phillips, and E. Torng. A better algorithm for an ancient scheduling problem. In Proc. of the 5th ACM-SIAM Symposium on Discrete Algorithms, pages 132\u2013140, 1994."},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"H. Kellerer, V. Kotov, M. G. Speranza, and Zs. Tuza. Semi on-line algorithms for the partition problem. Operations Research Letters. To appear.","DOI":"10.1016\/S0167-6377(98)00005-4"},{"key":"7_CR21","volume-title":"Technical Report Technical Report CMU-CS-94-144","author":"J. Sgall","year":"1994","unstructured":"J. Sgall. On-line scheduling on parallel machines. Technical Report Technical Report CMU-CS-94-144, Carnegie-Mellon University, Pittsburgh, PA, USA, 1994."}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49543-6_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T01:20:37Z","timestamp":1737076837000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49543-6_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540651420","9783540495437"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-49543-6_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}