{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:15:37Z","timestamp":1781345737006,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,6,19]],"date-time":"2016-06-19T00:00:00Z","timestamp":1466294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,19]]},"DOI":"10.1145\/2897518.2897572","type":"proceedings-article","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T13:04:07Z","timestamp":1465563847000},"page":"156-167","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Lift-and-round to improve weighted completion time on unrelated machines"],"prefix":"10.1145","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[{"name":"EPFL, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"44","volume-title":"FOCS","author":"Afrati Foto N.","year":"1999","unstructured":"Foto N. Afrati , Evripidis Bampis , Chandra Chekuri , David R. Karger , Claire Kenyon , Sanjeev Khanna , Ioannis Milis , Maurice Queyranne , Martin Skutella , Clifford Stein , and Maxim Sviridenko . Approximation schemes for minimizing average weighted completion time with release dates. In Foundations of Computer Science , FOCS , pages 32\u2013 44 , 1999 . Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, and Maxim Sviridenko. Approximation schemes for minimizing average weighted completion time with release dates. In Foundations of Computer Science, FOCS, pages 32\u201344, 1999."},{"key":"e_1_3_2_1_2_1","first-page":"30","volume-title":"Integer Programming and Combinatorial Optimization IPCO","author":"Alexander","year":"1999","unstructured":"Alexander A. Ageev and Maxim Sviridenko. Approximation algorithms for maximum coverage and max cut with given sizes of parts . In Integer Programming and Combinatorial Optimization IPCO , pages 17\u2013 30 , 1999 . Alexander A. Ageev and Maxim Sviridenko. Approximation algorithms for maximum coverage and max cut with given sizes of parts. In Integer Programming and Combinatorial Optimization IPCO, pages 17\u201330, 1999."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100271"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229163.2229168"},{"key":"e_1_3_2_1_5_1","unstructured":"4\n    This bound is loose and can also be obtained using independent randomized rounding instead of our negative-correlation rounding. The importance of the new rounding appears in the other case.  4 This bound is loose and can also be obtained using independent randomized rounding instead of our negative-correlation rounding. The importance of the new rounding appears in the other case."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250808"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060639"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132522"},{"key":"e_1_3_2_1_9_1","first-page":"116","volume-title":"FOCS","author":"Chakrabarty Deeparnab","year":"2009","unstructured":"Deeparnab Chakrabarty , Julia Chuzhoy , and Sanjeev Khanna . On allocating goods to maximize fairness. In Foundations of Computer Science , FOCS , pages 107\u2013 116 , 2009 . Deeparnab Chakrabarty, Julia Chuzhoy, and Sanjeev Khanna. On allocating goods to maximize fairness. In Foundations of Computer Science, FOCS, pages 107\u2013116, 2009."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/646254.684260"},{"key":"e_1_3_2_1_11_1","volume-title":"Handbook of Scheduling - Algorithms, Models, and Performance Analysis.","author":"Chekuri Chandra","year":"2004","unstructured":"Chandra Chekuri and Sanjeev Khanna . Approximation algorithms for minimizing averageweighted completion time . In Handbook of Scheduling - Algorithms, Models, and Performance Analysis. 2004 . Chandra Chekuri and Sanjeev Khanna. Approximation algorithms for minimizing averageweighted completion time. In Handbook of Scheduling - Algorithms, Models, and Performance Analysis. 2004."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327180"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133118"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1425(199903\/04)2:2<73::AID-JOS18>3.0.CO;2-Q"},{"key":"e_1_3_2_1_15_1","first-page":"293","volume-title":"Symposium on Discrete Algorithms, SODA","author":"Feige Uriel","year":"2008","unstructured":"Uriel Feige . On allocations that maximize fairness . In Symposium on Discrete Algorithms, SODA , pages 287\u2013 293 , 2008 . Uriel Feige. On allocations that maximize fairness. In Symposium on Discrete Algorithms, SODA, pages 287\u2013293, 2008."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147956"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019936223X"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789945.2789946"},{"key":"e_1_3_2_1_19_1","first-page":"151","volume-title":"Symposium on Discrete Algorithms, SODA","author":"Hall Leslie A.","year":"1996","unstructured":"Leslie A. Hall , David B. Shmoys , and Joel Wein . Scheduling to minimize average completion time: Off-line and on-line algorithms . In Symposium on Discrete Algorithms, SODA , pages 142\u2013 151 , 1996 . Leslie A. Hall, David B. Shmoys, and Joel Wein. Scheduling to minimize average completion time: Off-line and on-line algorithms. In Symposium on Discrete Algorithms, SODA, pages 142\u2013151, 1996."},{"key":"e_1_3_2_1_20_1","first-page":"366","volume-title":"IPCO","author":"Hoogeveen Han","year":"1998","unstructured":"Han Hoogeveen , Petra Schuurman , and Gerhard J. Woeginger . Non-approximability results for scheduling problems with minsum criteria. In Integer Programming and Combinatorial Optimization , IPCO , pages 353\u2013 366 , 1998 . Han Hoogeveen, Petra Schuurman, and Gerhard J. Woeginger. Non-approximability results for scheduling problems with minsum criteria. In Integer Programming and Combinatorial Optimization, IPCO, pages 353\u2013366, 1998."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215919"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-30162-4_240"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1552285.1552289"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.67"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194279057"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585872"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199357078"},{"key":"e_1_3_2_1_29_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_3_2_1_30_1","first-page":"964","volume-title":"ACM-SIAM Symposium on Discrete Algorithms, SODA","author":"Sethuraman Jay","year":"1999","unstructured":"Jay Sethuraman and Mark S. Squillante . Optimal scheduling of multiclass parallel machines . In ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 963\u2013 964 , 1999 . Jay Sethuraman and Mark S. Squillante. Optimal scheduling of multiclass parallel machines. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 963\u2013964, 1999."},{"key":"e_1_3_2_1_31_1","volume-title":"Personal communication","author":"Skutella Martin","year":"2015","unstructured":"Martin Skutella . Personal communication . Oct 2015 . Martin Skutella. Personal communication. Oct 2015."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375840"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301356"},{"issue":"59","key":"e_1_3_2_1_34_1","first-page":"U66","article-title":"Various optimizers for single-stage production","volume":"3","author":"Smith W. E.","year":"1956","unstructured":"W. E. Smith . Various optimizers for single-stage production . Naval Research Logistics , 3 : 59 \u02dd U66 , 1956 . W. E. Smith. Various optimizers for single-stage production. Naval Research Logistics, 3:59 \u02dd U66, 1956.","journal-title":"Naval Research Logistics"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/110851201"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_33"}],"event":{"name":"STOC '16: Symposium on Theory of Computing","location":"Cambridge MA USA","acronym":"STOC '16","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897572","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897572","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:55:57Z","timestamp":1750222557000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897572"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,19]]},"references-count":36,"alternative-id":["10.1145\/2897518.2897572","10.1145\/2897518"],"URL":"https:\/\/doi.org\/10.1145\/2897518.2897572","relation":{},"subject":[],"published":{"date-parts":[[2016,6,19]]},"assertion":[{"value":"2016-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}