{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:48:43Z","timestamp":1759063723888},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633976"},{"type":"electronic","value":"9783540695363"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63397-9_32","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T15:22:48Z","timestamp":1270480968000},"page":"416-429","source":"Crossref","is-referenced-by-count":27,"title":["Scheduling-LPs bear probabilities randomized approximations for min-sum criteria"],"prefix":"10.1007","author":[{"given":"Andreas S.","family":"Schulz","sequence":"first","affiliation":[]},{"given":"Martin","family":"Skutella","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, S. Kutten, and D. Peleg. Competitive distributed job scheduling. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, pages 571\u2013581, 1992.","DOI":"10.1145\/129712.129768"},{"key":"32_CR2","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"J. L. Bruno","year":"1974","unstructured":"J. L. Bruno, E. G. Coffman Jr., and R. Sethi. Scheduling independent tasks to reduce mean finishing time. Communications of the Association for Computing Machinery, 17:382\u2013387, 1974.","journal-title":"Communications of the Association for Computing Machinery"},{"key":"32_CR3","doi-asserted-by":"crossref","unstructured":"C. S. Chekuri, R. Johnson, R. Motwani, B. K. Natarajan, B. R. Rau, and M. Schlansker. Profile-driven instruction level parallel scheduling with applications to super blocks. December 1996. Proceedings of the 29th Annual International Symposium on Microarchitecture (MICRO-29), Paris, France.","DOI":"10.1109\/MICRO.1996.566450"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"S. Chakrabarti and S. Muthukrishnan. Resource scheduling for parallel database and scientific applications. June 1996. Proceedings of the 8th ACM Symposium on Parallel Algorithms and Architectures.","DOI":"10.1145\/237502.237577"},{"key":"32_CR5","unstructured":"C. S. Chekur\u00ef, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques for average completion time scheduling. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, pages 609\u2013618, 1997."},{"key":"32_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1007\/3-540-61440-0_166","volume-title":"Automata, Languages and Programming","author":"S. Chakrabarti","year":"1996","unstructured":"S. Chakrabarti, C. A. Phillips, A. S. Schulz, D. B. Shmoys, C. Stein, and J. Wein. Improved scheduling algorithms for minsum criteria. In F. Meyer auf der Heide and B. Monien, editors, Automata, Languages and Programming, number 1099 in Lecture Notes in Computer Science, pages 646\u2013657. Springer, Berlin, 1996. Proceedings of the 23rd International Colloquium (ICALP'96)."},{"key":"32_CR7","unstructured":"F A. Chudak and D. B. Shmoys. Approximation algorithms for precedenceconstrained scheduling problems on parallel machines that run at different speeds. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, pages 581\u2013590,1997."},{"key":"32_CR8","unstructured":"X. Deng, H. Liu, J. Long, and B. Xiao. Deterministic load balancing in computer networks. In Proceedings of the 2nd Annual IEEE Symposium on Parallel and Distributed Processing, pages 50\u201357, 1990."},{"key":"32_CR9","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0166-218X(90)90104-K","volume":"26","author":"M. E. Dyer","year":"1990","unstructured":"M. E. Dyer and L. A. Wolsey. Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics, 26:255\u2013270, 1990.","journal-title":"Discrete Applied Mathematics"},{"key":"32_CR10","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/0097-3165(73)90005-8","volume":"14","author":"P. Erdas","year":"1973","unstructured":"P. Erdas and J. L. Selfridge. On a combinatorial game. Journal of Combinatorial Theory A, 14:298\u2013301, 1973.","journal-title":"Journal of Combinatorial Theory A"},{"key":"32_CR11","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R. L. Graham","year":"1979","unstructured":"R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5:287\u2013326, 1979.","journal-title":"Annals of Discrete Mathematics"},{"key":"32_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/3-540-61310-2_22","volume-title":"Integer Programming and Combinatorial Optimization","author":"M. X. Goemans","year":"1996","unstructured":"M. X. Goemans. A supermodular relaxation for scheduling with release dates. In W. H. Cunningham, S. T. McCormick, and M. Queyranne, editors, Integer Programming and Combinatorial Optimization, number 1084 in Lecture Notes in Computer Science, pages 288\u2013300. Springer, Berlin, 1996. Proceedings of the 5th International IPCO Conference."},{"key":"32_CR13","unstructured":"M. X. Goemans. Improved approximation algorithms for scheduling with release dates. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, pages 591\u2013598, 1997."},{"key":"32_CR14","unstructured":"M. X. Goemans, M. Queyranne, A. S. Schulz, M. Skutella, and Y Wang, 1997. In preparation."},{"key":"32_CR15","volume-title":"Scheduling to minimize average completion time: Off-line and on-line approximation algorithms","author":"L. A. Hall","year":"1996","unstructured":"L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Preprint 516\/1996, Department of Mathematics, Technical University of Berlin, Berlin, Germany, 1996. To appear in Mathematics of Operations Research."},{"key":"32_CR16","unstructured":"L. A. Hall, D. B. Shmoys, and J. Wein. Scheduling to minimize average completion time: Off-line and on-line algorithms. In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms, pages 142\u2013151, 1996."},{"key":"32_CR17","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1137\/0215081","volume":"15","author":"T. Kawaguchi","year":"1986","unstructured":"T. Kawaguchi and S. Kyan. Worst case bound of an LRF schedule for the mean weighted flow-time problem. SIAM Journal on Computing, 15:1119\u20131129, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR18","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":"32_CR19","unstructured":"R. Motwani, J. Naor, and P Raghavan. Randomized approximation algorithms in combinatorial optimization. In D. S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, chapter 11. Thomson, 1996."},{"key":"32_CR20","doi-asserted-by":"crossref","unstructured":"R. Motwani and P Raghavan. Randomized Algorithms. Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"32_CR21","series-title":"Lecture Notes in Com puter Science","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/3-540-61680-2_48","volume-title":"Algorithms-ESA'96, volume 1136","author":"R. H. M\u00f6hring","year":"1996","unstructured":"R. H. M\u00f6hring, M. W. Sch\u00e4ffter, and A. S. Schulz. Scheduling jobs with communication delays: Using infeasible solutions for approximation. In J. Diaz and M. Serna, editors, Algorithms-ESA'96, volume 1136 of Lecture Notes in Com puter Science, pages 76\u201390. Springer, Berlin, 1996. Proceedings of the 4th Annual European Symposium on Algorithms."},{"key":"32_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/3-540-58218-5_27","volume-title":"Algorithm Theory-SWAT'94, number 824","author":"C. Phillips","year":"1994","unstructured":"C. Phillips, C. Stein, and J. Wein. Task scheduling in networks. In Algorithm Theory-SWAT'94, number 824 in Lecture Notes in Computer Science, pages 290\u2013301. Springer, Berlin, 1994. Proceedings of the 4th Scandinavian Workshop on Algorithm Theory."},{"key":"32_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/3-540-60220-8_53","volume-title":"Proceedings of the Fourth Workshop on Algorithms and Data Structures, number 955","author":"C. Phillips","year":"1995","unstructured":"C. Phillips, C. Stein, and J. Wein. Scheduling jobs that arrive over time. In Proceedings of the Fourth Workshop on Algorithms and Data Structures, number 955 in Lecture Notes in Computer Science, pages 86\u201397. Springer, Berlin, 1995."},{"key":"32_CR24","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":"32_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/3-540-61310-2_23","volume-title":"Integer Programming and Combinatorial Optimization, number 1084","author":"A. S. Schulz","year":"1996","unstructured":"A. S. Schulz. Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. In W. H. Cunningham, S. T. McCormick, and M. Queyranne, editors, Integer Programming and Combinatorial Optimization, number 1084 in Lecture Notes in Computer Science, pages 301\u2013315. Springer, Berlin, 1996. Proceedings of the 5th International IPCO Conference."},{"key":"32_CR26","unstructured":"J. Spencer. Ten Lectures on the Probabilistic Method. Number 52 in CBMS-NSF Reg. Conf. Ser. Appl. Math. SIAM, 1987."},{"key":"32_CR27","volume-title":"Random-based scheduling: New approximations and LP lower bounds","author":"A. S. Schulz","year":"1997","unstructured":"A. S. Schulz and M. Skutella. Random-based scheduling: New approximations and LP lower bounds. Preprint 549\/1997, Department of Mathematics, Technical University of Berlin, Berlin, Germany, February 1997. To appear in Springer Lecture Notes in Computer Science, Proceedings of the 1st International Symposium on Randomization and Approximation Techniques in Computer Science (Random' 97)."},{"key":"32_CR28","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"D. B. Shmoys","year":"1993","unstructured":"D. B. Shmoys and \u00c9. Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming, 62:461\u2013474, 1993.","journal-title":"Mathematical Programming"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63397-9_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T20:17:54Z","timestamp":1558988274000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63397-9_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633976","9783540695363"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-63397-9_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}