{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:41:41Z","timestamp":1725493301080},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662518"},{"type":"electronic","value":"9783540484813"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48481-7_12","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T23:49:40Z","timestamp":1193528980000},"page":"127-138","source":"Crossref","is-referenced-by-count":7,"title":["Convex Quadratic Programming Relaxations for Network Scheduling Problems"],"prefix":"10.1007","author":[{"given":"Martin","family":"Skutella","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,1,14]]},"reference":[{"key":"12_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. 128","DOI":"10.1145\/129712.129768"},{"key":"12_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. 128","journal-title":"Communications of the Association for Computing Machinery"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"S. J. Chung and K. G. Murty. Polynomially bounded ellipsoid algorithms for convex quadratic programming. In O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, editors, Nonlinear Programming 4, pages 439\u2013485. Academic Press, 1981. 134","DOI":"10.1016\/B978-0-12-468662-5.50021-5"},{"key":"12_CR4","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. 128"},{"key":"12_CR5","doi-asserted-by":"publisher","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. 129","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR6","unstructured":"M. X. Goemans. Improved approximation algorithms for scheduling with release dates. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 591\u2013598, 1997. 128"},{"key":"12_CR7","doi-asserted-by":"publisher","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. 128","journal-title":"Annals of Discrete Mathematics"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"22","author":"L. A. Hall","year":"1997","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. Mathematics of Operations Research, 22:513\u2013544, 1997. 128","journal-title":"Mathematics of Operations Research"},{"key":"12_CR9","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 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 142\u2013151, 1996. 128"},{"key":"12_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/3-540-69346-7_27","volume-title":"Integer Programming and Combinatorial Optimization","author":"H. Hoogeveen","year":"1998","unstructured":"H. Hoogeveen, P. Schuurman, and G. J. Woeginger. Non-approximability results for scheduling problems with minsum criteria. In R. E. Bixby, E. A. Boyd, and R. Z. R\u00edos-Mercado, editors, Integer Programming and Combinatorial Optimization, volume 1412 of Lecture Notes in Computer Science, pages 353\u2013366. Springer, Berlin, 1998. 137"},{"key":"12_CR11","first-page":"1108","volume":"20","author":"M. K. Kozlov","year":"1979","unstructured":"M. K. Kozlov, S. P. Tarasov, and L. G. Ha\u010dijan. Polynomial solvability of convex quadratic programming. Soviet Mathematics Doklady, 20:1108\u20131111, 1979. 134","journal-title":"Soviet Mathematics Doklady"},{"key":"12_CR12","doi-asserted-by":"publisher","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. 128, 129","journal-title":"Annals of Discrete Mathematics"},{"key":"12_CR13","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, pages 447\u2013481. Thomson, 1996. 135"},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1137\/0219021","volume":"19","author":"C. H. Papadimitriou","year":"1990","unstructured":"C. H. Papadimitriou and M. Yannakakis. Towards an architecture-independent analysis of parallel algorithms. SIAM Journal on Computing, 19:322\u2013328, 1990. 130","journal-title":"SIAM Journal on Computing"},{"key":"12_CR15","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1137\/S0895480194279057","volume":"10","author":"C. Phillips","year":"1997","unstructured":"C. Phillips, C. Stein, and J. Wein. Task scheduling in networks. SIAM Journal on Discrete Mathematics, 10:573\u2013598, 1997. 128","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"12_CR16","first-page":"199","volume":"82","author":"C. Phillips","year":"1998","unstructured":"C. Phillips, C. Stein, and J. Wein. Minimizing average completion time in the presence of release dates. Mathematical Programming, 82:199\u2013223, 1998. 130","journal-title":"Mathematical Programming"},{"key":"12_CR17","doi-asserted-by":"publisher","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. 135","journal-title":"Combinatorica"},{"key":"12_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/3-540-63397-9_32","volume-title":"Algorithms-ESA\u2019 97","author":"A. S. Schulz","year":"1997","unstructured":"A. S. Schulz and M. Skutella. Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria. In R. Burkard and G. J. Woeginger, editors, Algorithms-ESA\u2019 97, volume 1284 of Lecture Notes in Computer Science, pages 416\u2013429. Springer, Berlin, 1997. 128, 130, 134"},{"key":"12_CR19","unstructured":"J. Sethuraman and M. S. Squillante. Optimal scheduling of multiclass prallel machines. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 963\u2013964, 1999. 129"},{"key":"12_CR20","doi-asserted-by":"publisher","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. 129","journal-title":"Mathematical Programming"},{"key":"12_CR21","volume-title":"Approximation and Randomization in Scheduling","author":"M. Skutella","year":"1998","unstructured":"M. Skutella. Approximation and Randomization in Scheduling. PhD thesis, Technical University of Berlin, Germany, 1998. 130"},{"key":"12_CR22","doi-asserted-by":"crossref","unstructured":"M. Skutella. Semidefinite relaxations for parallel machine scheduling. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pages 472\u2013481, 1998. 129, 129, 130, 131, 132, 134, 136","DOI":"10.1109\/SFCS.1998.743498"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"M. Skutella. Convex Quadratic and Semidefinite Programming Relaxations in Scheduling. Manuscript, 1999. 130","DOI":"10.1007\/3-540-48481-7_12"},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W. E. Smith","year":"1956","unstructured":"W. E. Smith. Various optimizers for single-stage production. Naval Research and Logistics Quarterly, 3:59\u201366, 1956. 129","journal-title":"Naval Research and Logistics Quarterly"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA\u2019 99"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48481-7_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T02:20:55Z","timestamp":1556936455000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48481-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662518","9783540484813"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-48481-7_12","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}