Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines. Bansal, N., Srinivasan, A., & Svensson, O. *arXiv:1511.07826 [cs]*, November, 2015. arXiv: 1511.07826

Paper abstract bibtex

Paper abstract bibtex

We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a \$(3/2-c)\$-approximation algorithm for some fixed \$c{\textgreater}0\$, improving upon the long-standing bound of 3/2 (independently due to Skutella, Journal of the ACM, 2001, and Sethuraman & Squillante, SODA, 1999). To do this, we first introduce a new lift-and-project based SDP relaxation for the problem. This is necessary as the previous convex programming relaxations have an integrality gap of \$3/2\$. Second, we give a new general bipartite-rounding procedure that produces an assignment with certain strong negative correlation properties.

@article{bansal_lift-and-round_2015, title = {Lift-and-{Round} to {Improve} {Weighted} {Completion} {Time} on {Unrelated} {Machines}}, url = {http://arxiv.org/abs/1511.07826}, abstract = {We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a \$(3/2-c)\$-approximation algorithm for some fixed \$c{\textgreater}0\$, improving upon the long-standing bound of 3/2 (independently due to Skutella, Journal of the ACM, 2001, and Sethuraman \& Squillante, SODA, 1999). To do this, we first introduce a new lift-and-project based SDP relaxation for the problem. This is necessary as the previous convex programming relaxations have an integrality gap of \$3/2\$. Second, we give a new general bipartite-rounding procedure that produces an assignment with certain strong negative correlation properties.}, urldate = {2016-03-20TZ}, journal = {arXiv:1511.07826 [cs]}, author = {Bansal, Nikhil and Srinivasan, Aravind and Svensson, Ola}, month = nov, year = {2015}, note = {arXiv: 1511.07826}, keywords = {Computer Science - Data Structures and Algorithms} }

Downloads: 0

{"_id":"L9Na5utexFQ6B7aCX","bibbaseid":"bansal-srinivasan-svensson-liftandroundtoimproveweightedcompletiontimeonunrelatedmachines-2015","downloads":0,"creationDate":"2016-12-19T20:50:58.131Z","title":"Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines","author_short":["Bansal, N.","Srinivasan, A.","Svensson, O."],"year":2015,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","title":"Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines","url":"http://arxiv.org/abs/1511.07826","abstract":"We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a \\$(3/2-c)\\$-approximation algorithm for some fixed \\$c{\\textgreater}0\\$, improving upon the long-standing bound of 3/2 (independently due to Skutella, Journal of the ACM, 2001, and Sethuraman & Squillante, SODA, 1999). To do this, we first introduce a new lift-and-project based SDP relaxation for the problem. This is necessary as the previous convex programming relaxations have an integrality gap of \\$3/2\\$. Second, we give a new general bipartite-rounding procedure that produces an assignment with certain strong negative correlation properties.","urldate":"2016-03-20TZ","journal":"arXiv:1511.07826 [cs]","author":[{"propositions":[],"lastnames":["Bansal"],"firstnames":["Nikhil"],"suffixes":[]},{"propositions":[],"lastnames":["Srinivasan"],"firstnames":["Aravind"],"suffixes":[]},{"propositions":[],"lastnames":["Svensson"],"firstnames":["Ola"],"suffixes":[]}],"month":"November","year":"2015","note":"arXiv: 1511.07826","keywords":"Computer Science - Data Structures and Algorithms","bibtex":"@article{bansal_lift-and-round_2015,\n\ttitle = {Lift-and-{Round} to {Improve} {Weighted} {Completion} {Time} on {Unrelated} {Machines}},\n\turl = {http://arxiv.org/abs/1511.07826},\n\tabstract = {We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a \\$(3/2-c)\\$-approximation algorithm for some fixed \\$c{\\textgreater}0\\$, improving upon the long-standing bound of 3/2 (independently due to Skutella, Journal of the ACM, 2001, and Sethuraman \\& Squillante, SODA, 1999). To do this, we first introduce a new lift-and-project based SDP relaxation for the problem. This is necessary as the previous convex programming relaxations have an integrality gap of \\$3/2\\$. Second, we give a new general bipartite-rounding procedure that produces an assignment with certain strong negative correlation properties.},\n\turldate = {2016-03-20TZ},\n\tjournal = {arXiv:1511.07826 [cs]},\n\tauthor = {Bansal, Nikhil and Srinivasan, Aravind and Svensson, Ola},\n\tmonth = nov,\n\tyear = {2015},\n\tnote = {arXiv: 1511.07826},\n\tkeywords = {Computer Science - Data Structures and Algorithms}\n}\n\n","author_short":["Bansal, N.","Srinivasan, A.","Svensson, O."],"key":"bansal_lift-and-round_2015","id":"bansal_lift-and-round_2015","bibbaseid":"bansal-srinivasan-svensson-liftandroundtoimproveweightedcompletiontimeonunrelatedmachines-2015","role":"author","urls":{"Paper":"http://arxiv.org/abs/1511.07826"},"keyword":["Computer Science - Data Structures and Algorithms"],"downloads":0,"html":""},"search_terms":["lift","round","improve","weighted","completion","time","unrelated","machines","bansal","srinivasan","svensson"],"keywords":["computer science - data structures and algorithms"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}