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

N. Bansal, A. Srinivasan, O. Svensson

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

18 Citaten (Scopus)

Samenvatting

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.

Originele taal-2Engels
TitelSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
Plaats van productieCambridge, Ma
UitgeverijAssociation for Computing Machinery, Inc
Pagina's156-167
Aantal pagina's12
ISBN van elektronische versie978-1-4503-4132-5
DOI's
StatusGepubliceerd - 19 jun 2016
Evenement48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016) - Cambridge, Verenigde Staten van Amerika
Duur: 19 jun 201621 jun 2016

Congres

Congres48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016)
Land/RegioVerenigde Staten van Amerika
StadCambridge
Periode19/06/1621/06/16

Vingerafdruk

Duik in de onderzoeksthema's van 'Lift-and-round to improve weighted completion time on unrelated machines'. Samen vormen ze een unieke vingerafdruk.

Citeer dit