@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}
}

{"_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"]}