{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:13Z","timestamp":1725664093973},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582182"},{"type":"electronic","value":"9783540485773"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58218-5_27","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:37:43Z","timestamp":1330270663000},"page":"290-301","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Task scheduling in networks"],"prefix":"10.1007","author":[{"given":"Cynthia","family":"Phillips","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clifford","family":"Stein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joel","family":"Wein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, G. Kalai, M. Ricklin, and L. Stockmeyer. Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 334\u2013343, 1992.","DOI":"10.1109\/SFCS.1992.267757"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, S. Kutten, and D.Peleg. Competetive distributed job scheduling. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 571\u2013580, 1992.","DOI":"10.1145\/129712.129768"},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"J. L. Bruno","year":"1974","unstructured":"J.L. Bruno, E.G. Coffman, and R. Sethi. Scheduling independent tasks to reduce mean finishing time. Communications of the ACM, 17:382\u2013387, 1974.","journal-title":"Communications of the ACM"},{"issue":"3","key":"27_CR4","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"V. Chv\u00e1tal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233\u2013235, August 1979.","journal-title":"Mathematics of Operations Research"},{"key":"27_CR5","unstructured":"X. Deng, H. Liu, J. Long, and B. Xiao. Deterministic load balancing in computer networks. In Proceedings of 2nd IEEE Symposium on Parallel and Distributed Processing, 1992."},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"P. Fizzano, D. Karger, C. Stein, and J. Wein. Job scheduling in rings. In Proceedings of the 1994 ACM Symposium on Parallel Algorithms and Architectures, 1994.","DOI":"10.1145\/181014.181333"},{"key":"27_CR7","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":"27_CR8","first-page":"263","volume":"17","author":"R. L. Graham","year":"1969","unstructured":"R.L. Graham. Bounds on multiprocessing anomalies. SIAM Journal of Applied Mathematics, 17:263\u2013269, 1969.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"27_CR9","unstructured":"M. Grotschel, C. L. Monma, and M. Stoer. Design of survivable networks. In Handbook in Operations Research and Management Science. 1992. To appear."},{"key":"27_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(84)90035-X","volume":"5","author":"D. Gusfield","year":"1984","unstructured":"D. Gusfield. Bounds for naive multiple machine scheduling with release times and deadlines. Journal of Algorithms, 5:1\u20136, 1984.","journal-title":"Journal of Algorithms"},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"L. Hall and D. B. Shmoys. Approximation schemes for constrained scheduling problems. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 134\u2013141. IEEE, October 1989.","DOI":"10.1109\/SFCS.1989.63468"},{"key":"27_CR12","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. Journal of the ACM, 34:144\u2013162, 1987.","journal-title":"Journal of the ACM"},{"key":"27_CR13","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"D. S. Hochbaum","year":"1988","unstructured":"D.S. Hochbaum and D.B. Shmoys. A polynomial approximation scheme for machine scheduling on uniform processors: using the dual approximation approach. SIAM Journal on Computing, 17:539\u2013551, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"27_CR14","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1287\/opre.21.3.846","volume":"21","author":"W. Horn","year":"1973","unstructured":"W. Horn. Minimizing average flow time with parallel machines. Operations Research, 21:846\u2013847, 1973.","journal-title":"Operations Research"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"E.L. Lawler, J.K. Lenstra, A.H.G. Rinooy Kan, and D.B. Shmoys. Sequencing and scheduling: Algorithms and complexity. In S.C. Graves, A.H.G. Rinnooy Kan, and P.H. Zipkin, editors, Handbooks in Operations Research and Management Science, Vol 4., Logistics of Production and Inventory, pages 445\u2013522. North-Holland, 1993.","DOI":"10.1016\/S0927-0507(05)80189-6"},{"issue":"3","key":"27_CR16","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1002\/j.1538-7305.1989.tb00318.x","volume":"68","author":"D. N. Lee","year":"1989","unstructured":"D. N. Lee, K. T. Medhi, J. L. Strand, R. G. Cox, and S. Chen. Solving large telecommunications network loading problems. AT&T Technical Journal, 68(3):48\u201356, 1989.","journal-title":"AT&T Technical Journal"},{"key":"27_CR17","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"J. K. Lenstra","year":"1977","unstructured":"J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343\u2013362, 1977.","journal-title":"Annals of Discrete Mathematics"},{"key":"27_CR18","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 \u00c9. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46:259\u2013271, 1990.","journal-title":"Mathematical Programming"},{"key":"27_CR19","unstructured":"D. Peleg, 1992. Private communication."},{"key":"27_CR20","unstructured":"S. Plotkin, D. B. Shmoys, and E. Tardos. Fast approximation algorithms for fractional packing and covering problems. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991. To appear."},{"key":"27_CR21","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"P. Raghavan. Probabilistic construction of deterministic algorithms: approximating packing integer programs. Journal of Computer and System Sciences, 37:130\u2013143, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR22","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"P. Raghavan and C. D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7:365\u2013374, 1987.","journal-title":"Combinatorica"},{"key":"27_CR23","unstructured":"D. B. Shmoys, C. Stein, and J. Wein. Improved approximation algorithms for shop scheduling problems. In Proceedings of the 2nd ACM-SIAM Symposium on Discrete Algorithms, pages 148\u2013157, January 1991. To appear in Siam J. Computing."},{"key":"27_CR24","unstructured":"D. B. Shmoys and E. Tardos. Scheduling parallel machines with costs. In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, pages 448\u2013455, January 1993."},{"key":"27_CR25","doi-asserted-by":"crossref","unstructured":"D. B. Shmoys, J. Wein, and D.P. Williamson. Scheduling parallel machines on-line. SIAM Journal on Computing, 1994. To appear.","DOI":"10.1137\/S0097539793248317"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '94"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58218-5_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T06:34:26Z","timestamp":1640932466000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_27"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"30 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}