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

N. Bansal, A. Srinivasan, O. Svensson

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

18 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 languageEnglish
Title of host publicationSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
Place of PublicationCambridge, Ma
PublisherAssociation for Computing Machinery, Inc
Pages156-167
Number of pages12
ISBN (Electronic)978-1-4503-4132-5
DOIs
Publication statusPublished - 19 Jun 2016
Event48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016) - Cambridge, United States
Duration: 19 Jun 201621 Jun 2016

Conference

Conference48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016)
Country/TerritoryUnited States
CityCambridge
Period19/06/1621/06/16

Keywords

  • Approximation algorithms
  • Rounding theorems
  • Scheduling
  • Semidefinite programming

Fingerprint

Dive into the research topics of 'Lift-and-round to improve weighted completion time on unrelated machines'. Together they form a unique fingerprint.

Cite this