Lift-and-round to improve weighted completion time on unrelated machines

N. Bansal; A. Srinivasan; O. Svensson

doi:10.1145/2897518.2897572

Lift-and-round to improve weighted completion time on unrelated machines

N. Bansal
, A. Srinivasan
, O. Svensson

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

34 Citations (Scopus)

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 > 0, improving upon the long-standing bound of 3/2. 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.

Original language	English
Title of host publication	STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
Place of Publication	Cambridge, Ma
Publisher	Association for Computing Machinery, Inc.
Pages	156-167
Number of pages	12
ISBN (Electronic)	978-1-4503-4132-5
DOIs	https://doi.org/10.1145/2897518.2897572
Publication status	Published - 19 Jun 2016
Event	48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016) - Cambridge, United States Duration: 19 Jun 2016 → 21 Jun 2016

Conference

Conference	48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016)
Country/Territory	United States
City	Cambridge
Period	19/06/16 → 21/06/16

Keywords

Approximation algorithms
Rounding theorems
Scheduling
Semidefinite programming

Access to Document

10.1145/2897518.2897572

Cite this

@inproceedings{114453f8f21f48fa97f8aeefa9b0b7b3,

title = "Lift-and-round to improve weighted completion time on unrelated machines",

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 > 0, improving upon the long-standing bound of 3/2. 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.",

keywords = "Approximation algorithms, Rounding theorems, Scheduling, Semidefinite programming",

author = "N. Bansal and A. Srinivasan and O. Svensson",

year = "2016",

month = jun,

day = "19",

doi = "10.1145/2897518.2897572",

language = "English",

pages = "156--167",

booktitle = "STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing",

publisher = "Association for Computing Machinery, Inc.",

address = "United States",

note = "48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016) ; Conference date: 19-06-2016 Through 21-06-2016",

}

Bansal, N, Srinivasan, A & Svensson, O 2016, Lift-and-round to improve weighted completion time on unrelated machines. in STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, Inc., Cambridge, Ma, pp. 156-167, 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), Cambridge, United States, 19/06/16. https://doi.org/10.1145/2897518.2897572

Lift-and-round to improve weighted completion time on unrelated machines. / Bansal, N.; Srinivasan, A.; Svensson, O.
STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Cambridge, Ma: Association for Computing Machinery, Inc., 2016. p. 156-167.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Lift-and-round to improve weighted completion time on unrelated machines

AU - Bansal, N.

AU - Srinivasan, A.

AU - Svensson, O.

PY - 2016/6/19

Y1 - 2016/6/19

N2 - 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 > 0, improving upon the long-standing bound of 3/2. 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.

AB - 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 > 0, improving upon the long-standing bound of 3/2. 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.

KW - Approximation algorithms

KW - Rounding theorems

KW - Scheduling

KW - Semidefinite programming

UR - https://www.scopus.com/pages/publications/84979302744

U2 - 10.1145/2897518.2897572

DO - 10.1145/2897518.2897572

M3 - Conference contribution

AN - SCOPUS:84979302744

SP - 156

EP - 167

BT - STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing

PB - Association for Computing Machinery, Inc.

CY - Cambridge, Ma

T2 - 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016)

Y2 - 19 June 2016 through 21 June 2016

ER -

Lift-and-round to improve weighted completion time on unrelated machines

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this