{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T01:22:35Z","timestamp":1768267355899,"version":"3.49.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2009,8,1]],"date-time":"2009-08-01T00:00:00Z","timestamp":1249084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000030","name":"Centers for Disease Control and Prevention","doi-asserted-by":"publisher","award":["2506055-01"],"award-info":[{"award-number":["2506055-01"]}],"id":[{"id":"10.13039\/100000030","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-0845700CCR-0208005CNS-0626636"],"award-info":[{"award-number":["CNS-0845700CCR-0208005CNS-0626636"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000057","name":"National Institute of General Medical Sciences","doi-asserted-by":"publisher","award":["U01 GM070694-05"],"award-info":[{"award-number":["U01 GM070694-05"]}],"id":[{"id":"10.13039\/100000057","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000774","name":"Defense Threat Reduction Agency","doi-asserted-by":"publisher","award":["HDTRA1-07-C-0113"],"award-info":[{"award-number":["HDTRA1-07-C-0113"]}],"id":[{"id":"10.13039\/100000774","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0626864CNS-0831633"],"award-info":[{"award-number":["CNS-0626864CNS-0831633"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0426683"],"award-info":[{"award-number":["CNS-0426683"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0845700CCR-0208005CNS-0626636"],"award-info":[{"award-number":["CNS-0845700CCR-0208005CNS-0626636"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000077","name":"Division of Social and Economic Sciences","doi-asserted-by":"publisher","award":["SES-0729441"],"award-info":[{"award-number":["SES-0729441"]}],"id":[{"id":"10.13039\/100000077","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>\n            We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming-, quadratic programming-, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. This algorithm leads to the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan\n            <jats:italic>simultaneously<\/jats:italic>\n            exhibit the current-best individual approximations for these criteria; (ii) better-than-two approximation guarantees for scheduling to minimize the\n            <jats:italic>\n              L\n              <jats:sub>p<\/jats:sub>\n            <\/jats:italic>\n            norm of the vector of machine-loads, for all 1 &lt;\n            <jats:italic>p<\/jats:italic>\n            &lt; \u221e; and (iii) the first constant-factor multicriteria approximation algorithms that can handle the weighted completion-time and\n            <jats:italic>any<\/jats:italic>\n            given collection of integer\n            <jats:italic>\n              L\n              <jats:sub>p<\/jats:sub>\n            <\/jats:italic>\n            norms. Our algorithm has a natural interpretation as a melding of linear-algebraic and probabilistic approaches. Via this view, it yields a common generalization of rounding theorems due to Karp et al. [1987] and Shmoys &amp; Tardos [1993], and leads to improved approximation algorithms for the problem of scheduling with resource-dependent processing times introduced by Grigoriev et al. [2007].\n          <\/jats:p>","DOI":"10.1145\/1552285.1552289","type":"journal-article","created":{"date-parts":[[2009,8,24]],"date-time":"2009-08-24T14:08:31Z","timestamp":1251122911000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["A unified approach to scheduling on unrelated parallel machines"],"prefix":"10.1145","volume":"56","author":[{"given":"V. S. Anil","family":"Kumar","sequence":"first","affiliation":[{"name":"Virginia Tech., Blacksburg, Virginia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhav V.","family":"Marathe","sequence":"additional","affiliation":[{"name":"Virginia Tech., Blacksburg, Virginia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinivasan","family":"Parthasarathy","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, Hawthorne, New York"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Maryland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,8,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Alon N.","unstructured":"Alon , N. , Azar , Y. , Woeginger , G. J. , and Yadid , T . 1997. Approximation schemes for scheduling . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 493--500. Alon, N., Azar, Y., Woeginger, G. J., and Yadid, T. 1997. Approximation schemes for scheduling. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 493--500."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Aslam J.","unstructured":"Aslam , J. , Rasala , A. , Stein , C. , and Young , N . 1999. Improved bicriteria existence theorems for scheduling . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 846--847. Aslam, J., Rasala, A., Stein, C., and Young, N. 1999. Improved bicriteria existence theorems for scheduling. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 846--847."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, 383--391","author":"Awerbuch B.","unstructured":"Awerbuch , B. , Azar , Y. , Grove , E. F. , Kao , M.-Y. , Krishnan , P. , and Vitter , J. S . 1995. Load balancing in the Lp norm . In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, 383--391 . Awerbuch, B., Azar, Y., Grove, E. F., Kao, M.-Y., Krishnan, P., and Vitter, J. S. 1995. Load balancing in the Lp norm. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, 383--391."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060639"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.02.003"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science. Springer-Verlag","author":"Azar Y.","unstructured":"Azar , Y. , and Taub , S . 2004. All-norm approximation for scheduling on identical machines . In Proceedings of the Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science. Springer-Verlag , Berlin, Germany, 298--310. Azar, Y., and Taub, S. 2004. All-norm approximation for scheduling on identical machines. In Proceedings of the Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany, 298--310."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204021"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147956"},{"key":"e_1_2_1_9_1","volume-title":"Tech. Rep. CMU-CS-02-203","author":"Goel A.","year":"2002","unstructured":"Goel , A. , and Meyerson , A . 2002 . Simultaneous optimization via approximate majorization for concave profits or convex costs. Tech. Rep. CMU-CS-02-203 , Carnegie-Mellon University , Pittsburgh . Goel, A., and Meyerson, A. 2002. Simultaneous optimization via approximate majorization for concave profits or convex costs. Tech. Rep. CMU-CS-02-203, Carnegie-Mellon University, Pittsburgh."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11496915_14"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0059-3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840353"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1752"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.21"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250947"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Lawler E. L. Lenstra J. K. Rinnooy Kan A. H. G. and Shmoys D. B. 1993. Sequencing and Scheduling: Algorithms and Complexity. Elsevier Amsterdam The Netherlands.  Lawler E. L. Lenstra J. K. Rinnooy Kan A. H. G. and Shmoys D. B. 1993. Sequencing and Scheduling: Algorithms and Complexity. Elsevier Amsterdam The Netherlands.","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<203::AID-JOS26>3.0.CO;2-5"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585178"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375840"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030106"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(97)00025-4"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1552285.1552289","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1552285.1552289","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:04Z","timestamp":1750253404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1552285.1552289"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1145\/1552285.1552289"],"URL":"https:\/\/doi.org\/10.1145\/1552285.1552289","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8]]},"assertion":[{"value":"2007-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-08-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}