{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T22:34:23Z","timestamp":1772490863393,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540649175","type":"print"},{"value":"9783540683117","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0029569","type":"book-chapter","created":{"date-parts":[[2005,12,6]],"date-time":"2005-12-06T14:47:06Z","timestamp":1133880426000},"page":"178-195","source":"Crossref","is-referenced-by-count":67,"title":["On-line load balancing"],"prefix":"10.1007","author":[{"given":"Yossi","family":"Azar","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,11,22]]},"reference":[{"key":"8_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":"8_CR2","unstructured":"M. Andrews. Constant factor bounds for on-line load balancing on related machines. Manuscript."},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"M. Andrews, M. Goemans, and L. Zhang. Improved bounds for on-line load balancing. In COCOON'96, 1996.","DOI":"10.1007\/3-540-61332-3_133"},{"key":"8_CR4","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.","DOI":"10.1145\/167088.167248"},{"key":"8_CR5","unstructured":"A. Avidor, Y. Azar, and J. Sgall. Ancient and new algorithms for load balancing in the l p norm. In Proc. 9th ACM-SIAM Symp. on Discrete Algorithms, pages 426\u2013435, 1998."},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, E. Grove, M. Kao, P. Krishnan, and J. Vitter. Load balancing in the l p norm. In Proc. 36th IEEE Symp. on Found. of Comp. Science, pages 383\u2013391, 1995.","DOI":"10.1109\/SFCS.1995.492494"},{"key":"8_CR7","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":"8_CR8","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.","DOI":"10.1109\/SFCS.1992.267770"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Y. Azar and L. Epstein. On-line load balancing of temporary tasks on identical machines. In 5th Israeli Symposium on Theory of Computing and Systems, pages 119\u2013125, 1997.","DOI":"10.1109\/ISTCS.1997.595163"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Y. Azar, B. Kalyanasundaram, S. Plotkin, K. Pruhs, and O. Waarts. Online load balancing of temporary tasks. In Workshop on Algorithms and Data Structures, pages 119\u2013130, 1993.","DOI":"10.1007\/3-540-57155-8_241"},{"key":"8_CR11","unstructured":"Y. Azar, J. Naor, and R. Rom. The competitiveness of on-line assignments. In Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, pages 203\u2013210, 1992."},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Y. Azar and O. Regev. On-line bin stretching. Manuscript, 1997.","DOI":"10.1007\/3-540-49543-6_7"},{"key":"8_CR13","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1006\/jcss.1995.1074","volume":"51","author":"Y. Bartal","year":"1995","unstructured":"Y. Bartal, A. Fiat, H. Karloff, and R. Vohra. New algorithms for an ancient scheduling problem. Journal of Computer and System Sciences, 51:359\u2013366, 1995.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR14","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0020-0190(94)00026-3","volume":"50","author":"Y. Bartal","year":"1994","unstructured":"Y. Bartal, H. Karloff, and Y. Rabani. A better lower bound for on-line scheduling. Information Processing Letters, 50:113\u2013116, 1994.","journal-title":"Information Processing Letters"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Y. Bartal and S. Leonardi. On-line routing in all-optical networks. In Proc. 24rd International Colloquium on Automata, Languages, and Programming, 1997.","DOI":"10.1007\/3-540-63165-8_207"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"P. Berman, M. Charikar, and M. Karpinski. A note on on-line load balancing for related machines. In 5th Annual Workshop on Algorithms and Data Structures, pages 116\u2013125, 1997.","DOI":"10.1007\/3-540-63307-3_52"},{"key":"8_CR17","unstructured":"R. Boppana and A. Floratos. Load balancing in the euclidean norm. Manuscript, 1997."},{"key":"8_CR18","doi-asserted-by":"crossref","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. J. Woeginger. Lower bounds for randomized online scheduling. Information Processing Letters, 51:219\u2013222, 1994.","journal-title":"Information Processing Letters"},{"key":"8_CR19","doi-asserted-by":"crossref","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":"8_CR20","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"Y. Cho","year":"1988","unstructured":"Y. Cho and S. Sahni. Bounds for list schedules on uniform processors. SIAM Journal on Computing, 9:91\u2013103, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"8_CR21","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's list scheduling. SIAM J. Computing, 22:349\u2013355, 1993.","journal-title":"SIAM J. Computing"},{"key":"8_CR22","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 multiprocessing anomalies. Bell System Technical Journal, 45:1563\u20131581, 1966.","journal-title":"Bell System Technical Journal"},{"key":"8_CR23","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"},{"key":"8_CR24","doi-asserted-by":"crossref","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:539\u2013551, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"8_CR25","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D. S. Hochbaum","year":"1987","unstructured":"Dorit S. Hochbaum and David 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":"8_CR26","unstructured":"P. Indyk, 1996. Personal communication."},{"key":"8_CR27","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1006\/jagm.1996.0019","volume":"20","author":"D. R. Karger","year":"1996","unstructured":"D. R. Karger, S. J. Phillips, and E. Torng. A better algorithm for an ancient scheduling problem. J. Algorithms, 20:132\u2013140, 1996.","journal-title":"J. Algorithms"},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for online bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 352\u2013358, Baltimore, Maryland, May 1990.","DOI":"10.1145\/100216.100262"},{"key":"8_CR29","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, 1998. To appear.","DOI":"10.1016\/S0167-6377(98)00005-4"},{"key":"8_CR30","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J.K. Lenstra","year":"1990","unstructured":"J.K. Lenstra, D.B. Shmoys, and E. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Math. Prog., 46:259\u2013271, 1990.","journal-title":"Math. Prog."},{"key":"8_CR31","doi-asserted-by":"crossref","unstructured":"S. Phillips and J. Westbrook. On-line load balancing and network flow. In Proc. 25th ACM Symposium on Theory of Computing, pages 402\u2013411, 1993.","DOI":"10.1145\/167088.167201"},{"key":"8_CR32","unstructured":"S. Plotkin and Y. Ma. An improved lower bound for load balancing of tasks with unknown duration. Manuscript."},{"key":"8_CR33","doi-asserted-by":"crossref","unstructured":"S. Seiden. Randomized algorithms for that ancient scheduling problem. In 5th annual Workshop on Algorithms and Data Structures, pages 210\u2013223, 1997.","DOI":"10.1007\/3-540-63307-3_61"},{"key":"8_CR34","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0020-0190(97)00093-8","volume":"63","author":"J. Sgall","year":"1997","unstructured":"J. Sgall. A lower bound for randomized on-line multiprocessor scheduling. Inforation Processing Letters, 63:51\u201355, 1997.","journal-title":"Inforation Processing Letters"},{"key":"8_CR35","doi-asserted-by":"crossref","first-page":"1313","DOI":"10.1137\/S0097539793248317","volume":"24","author":"D. B. Shmoys","year":"1995","unstructured":"D. B. Shmoys, J. Wein, and D. P. Williamson. Scheduling parallel machines online. SIAM Journal on Computing, 24:1313\u20131331, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"8_CR36","doi-asserted-by":"crossref","unstructured":"J. Westbrook. Load balancing for response time. In 3rd Annual European Symposium on Algorithms, 1995.","DOI":"10.1007\/3-540-60313-1_155"}],"container-title":["Lecture Notes in Computer Science","Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029569","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T08:46:33Z","timestamp":1736153193000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029569"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540649175","9783540683117"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/bfb0029569","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]}}}