{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T04:02:10Z","timestamp":1748836930381,"version":"3.41.0"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319249704"},{"type":"electronic","value":"9783319249711"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-24971-1_12","type":"book-chapter","created":{"date-parts":[[2016,1,11]],"date-time":"2016-01-11T09:18:01Z","timestamp":1452503881000},"page":"125-132","source":"Crossref","is-referenced-by-count":0,"title":["Convex Quadratic Programming in Scheduling"],"prefix":"10.1007","author":[{"given":"Martin","family":"Skutella","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,1,12]]},"reference":[{"key":"12_CR1","unstructured":"Bruno, J.L., Coffman Jr. E.G., Sethi, R.: Scheduling independent tasks to reduce mean finishing time. Commun. Assoc. Comput. Mach. 17, 382\u2013387 (1974)"},{"key":"12_CR2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"12_CR3","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1287\/ijoc.13.2.157.10520","volume":"13","author":"H Hoogeveen","year":"2001","unstructured":"Hoogeveen, H., Schuurman, P., Woeginger, G.J.: Non-approximability results for scheduling problems with minsum criteria. INFORMS J. Comput. 13, 157\u2013168 (2001)","journal-title":"INFORMS J. Comput."},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1137\/0215081","volume":"15","author":"T Kawaguchi","year":"1986","unstructured":"Kawaguchi, T., Kyan, S.: Worst case bound of an LRF schedule for the mean weighted flow-time problem. SIAM J. Comput. 15, 1119\u20131129 (1986)","journal-title":"SIAM J. Comput."},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Schulz, A.S., Skutella, M.: Random-based scheduling: New approximations and LP lower bounds. In: Rolim, J. (ed.) Randomization and Approximation Techniques in Computer Science. Lecture Notes in Computer Science, vol. 1269, pp. 119\u2013133. Springer (1997)","DOI":"10.1007\/3-540-63248-4_11"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/S0895480199357078","volume":"15","author":"AS Schulz","year":"2002","unstructured":"Schulz, A.S., Skutella, M.: Scheduling unrelated machines by randomized rounding. SIAM J. Discret. Math. 15, 450\u2013469 (2002)","journal-title":"SIAM J. Discret. Math."},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<203::AID-JOS26>3.0.CO;2-5","volume":"2","author":"P Schuurman","year":"1999","unstructured":"Schuurman, P., Woeginger, G.J.: Polynomial time approximation algorithms for machine scheduling: Ten open problems. J. Sched. 2, 203\u2013213 (1999)","journal-title":"J. Sched."},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/j.orl.2011.06.007","volume":"39","author":"U Schwiegelshohn","year":"2011","unstructured":"Schwiegelshohn, U.: An alternative proof of the Kawaguchi-Kyan bound for the largest-ratio-first rule. Oper. Res. Lett. 39, 255\u2013259 (2011)","journal-title":"Oper. Res. Lett."},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Sethuraman, J., Squillante, M.S.: Optimal scheduling of multiclass parallel machines. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 963\u2013964, Baltimore (1999)","DOI":"10.1145\/301453.301483"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Sitters, R.A.: Approximability of average completion time scheduling on unrelated machines. In: Halperin, D., Mehlhorn, K. (eds.) Algorithms\u2013ESA\u201908. Lecture Notes in Computer Science, vol. 5193, pp. 768\u2013779. Springer (2008)","DOI":"10.1007\/978-3-540-87744-8_64"},{"key":"12_CR11","unstructured":"Skutella, M.: Approximation and Randomization in Scheduling. Ph.D. thesis, Technische Universit\u00e4t Berlin, Germany (1998)"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Skutella, M.: Semidefinite relaxations for parallel machine scheduling. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pp. 472\u2013481. Palo Alto (1998)","DOI":"10.1109\/SFCS.1998.743498"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Skutella, M.: Convex quadratic programming relaxations for network scheduling problems. In: Ne\u0161et\u0159il, J. (ed.) Algorithms\u2013ESA\u201999. Lecture Notes in Computer Science, vol. 1643, pp. 127\u2013138. Springer (1999)","DOI":"10.1007\/3-540-48481-7_12"},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1145\/375827.375840","volume":"48","author":"M Skutella","year":"2001","unstructured":"Skutella, M.: Convex quadratic and semidefinite programming relaxations in scheduling. J. ACM 48, 206\u2013242 (2001)","journal-title":"J. ACM"},{"key":"12_CR15","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1287\/moor.25.1.63.15212","volume":"25","author":"M Skutella","year":"2000","unstructured":"Skutella, M., Woeginger, G.J.: A PTAS for minimizing the total weighted completion time on identical parallel machines. Math. Oper. Res. 25, 63\u201375 (2000)","journal-title":"Math. Oper. Res."},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"WE Smith","year":"1956","unstructured":"Smith, W.E.: Various optimizers for single-stage production. Nav. Res. Log. Q. 3, 59\u201366 (1956)","journal-title":"Nav. Res. Log. Q."}],"container-title":["Gems of Combinatorial Optimization and Graph Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-24971-1_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T03:00:31Z","timestamp":1748746831000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-24971-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319249704","9783319249711"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-24971-1_12","relation":{},"subject":[],"published":{"date-parts":[[2015]]}}}