{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T12:10:24Z","timestamp":1737288624262,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540404934"},{"type":"electronic","value":"9783540450610"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_85","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T15:54:04Z","timestamp":1184601244000},"page":"1108-1122","source":"Crossref","is-referenced-by-count":2,"title":["Online Load Balancing Made Simple: Greedy Strikes Back"],"prefix":"10.1007","author":[{"given":"Pilu","family":"Crescenzi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giorgio","family":"Gambosi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gaia","family":"Nicosia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Penna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Walter","family":"Unger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"85_CR1","doi-asserted-by":"crossref","unstructured":"S. Albers. Better bounds for on-line scheduling. Proc. of the 29th ACM Symp. on Theory of Computing (STOC), pages 130\u2013139, 1997.","DOI":"10.1145\/258533.258566"},{"key":"85_CR2","doi-asserted-by":"crossref","unstructured":"Y. Azar. On-line load balancing, chapter in \u201cOn-line Algorithms-The state of the Art\u201d, A. Fiat and G. Woeginger (eds.). Springer Verlag, 1998.","DOI":"10.1007\/BFb0029569"},{"key":"85_CR3","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0304-3975(94)90153-8","volume":"130","author":"Y. Azar","year":"1994","unstructured":"Y. Azar, A. Broder, and A. Karlin. Online load balancing. Theoretical Computer Science, 130:73\u201384, 1994.","journal-title":"Theoretical Computer Science"},{"key":"85_CR4","doi-asserted-by":"crossref","unstructured":"Y. Azar and L. Epstein. On-line load balancing of temporary tasks on identical machines. Proc. of the 5th Israeli Symposium on Theory of Computing and Systems (ISTCS), pages 119\u2013125, 1997.","DOI":"10.1109\/ISTCS.1997.595163"},{"key":"85_CR5","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1006\/jagm.1995.0799","volume":"22","author":"Y. Azar","year":"1997","unstructured":"Y. Azar, B. Kalyanasundaram, S. Plotkin, K. Pruhs, and O. Waarts. Online load balancing of temporary tasks. Journal of Algorithms, 22:93\u2013110, 1997.","journal-title":"Journal of Algorithms"},{"key":"85_CR6","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1006\/jagm.1995.1008","volume":"18","author":"Y. Azar","year":"1995","unstructured":"Y. Azar, J. Naor, and R. Rom. The competitiveness of online assignments. Journal of Algorithms, 18:221\u2013237, 1995.","journal-title":"Journal of Algorithms"},{"issue":"2","key":"85_CR7","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1137\/S0097539798346135","volume":"31","author":"A. Bar-Noy","year":"2001","unstructured":"A. Bar-Noy, A. Freund, and J. Naor. On-line load balancing in a hierarchical server topology. SIAM Journal on Computing, 31(2):527\u2013549, 2001. Preliminary version in Proc. of the 7th Annual European Symposium on Algorithms, ESA\u201999.","journal-title":"SIAM Journal on Computing"},{"key":"85_CR8","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/BF01918335","volume":"12","author":"D. Braess","year":"1968","unstructured":"D. Braess. Ueber ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung, 12:258\u2013268, 1968.","journal-title":"Unternehmensforschung"},{"key":"85_CR9","doi-asserted-by":"crossref","unstructured":"P. Crescenzi, G. Gambosi, and P. Penna. On-line algorithms for the channel assignment problem in cellular networks. In Proc. of the 4th ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing (DIALM), pages 1\u20137, 2000. Full version to appear in Discrete Applied Mathematics.","DOI":"10.1145\/345848.345851"},{"key":"85_CR10","doi-asserted-by":"crossref","unstructured":"P. Crescenzi, G. Gambosi, and P. Penna. On-line load balancing made simple: Greedy strikes back. Technical report, Universit\u00e0 di Salerno, 2003. Electronic version available at http:\/\/www.dia.unisa.it\/~penna.","DOI":"10.1007\/3-540-45061-0_85"},{"key":"85_CR11","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R. Graham","year":"1966","unstructured":"R. Graham. Bounds for certain multiprocessor anomalies. Bell System Technical Journal, 45:1563\u20131581, 1966.","journal-title":"Bell System Technical Journal"},{"key":"85_CR12","first-page":"263","volume":"17","author":"R. Graham","year":"1969","unstructured":"R. Graham. Bounds on multiprocessor timing anomalies. SIAM J. Appl. Math., 17:263\u2013269, 1969.","journal-title":"SIAM J. Appl. Math."},{"key":"85_CR13","doi-asserted-by":"crossref","unstructured":"S. Guha and S. Khuller. Greedy strikes back: Improved facility location algorithms. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 1998.","DOI":"10.1006\/jagm.1998.0993"},{"key":"85_CR14","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"E. Tard\u00f2s","year":"1990","unstructured":"E. Tard\u00f2s J.K. Lenstra, D.B. Shmoys. Approximation algorithms for scheduling unrelated parallel machines. Math. Programming, 46:259\u2013271, 1990.","journal-title":"Math. Programming"},{"key":"85_CR15","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/0041-1647(70)90196-6","volume":"4","author":"J. D. Murchland","year":"1070","unstructured":"J. D. Murchland. Braess\u2019s paradox of traffic flow. Transportation Research, 4:391\u2013394, 1070.","journal-title":"Transportation Research"},{"issue":"3","key":"85_CR16","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/PL00009214","volume":"21","author":"S. Phillips","year":"1998","unstructured":"S. Phillips and J. Westbrook. Online load balancing and network flow. Algorithmica, 21(3):245\u2013261, 1998.","journal-title":"Algorithmica"},{"issue":"6","key":"85_CR17","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/S0020-0190(97)00085-9","volume":"62","author":"S. Y. Ma","year":"1997","unstructured":"Serge Y. Ma and A. Plotkin. An improved lower bound for load balancing of tasks with unknown duration. Information Processing Letters, 62(6):301\u2013303, 1997.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_85","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T11:42:32Z","timestamp":1737286952000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_85"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-45061-0_85","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}