Semidefinite Relaxations for Parallel Machine Scheduling

dc.contributor.authorSkutella, Martin
dc.date.accessioned2021-12-17T10:14:40Z
dc.date.available2021-12-17T10:14:40Z
dc.date.issued1998
dc.description.abstractWe consider the problem of scheduling unrelated parallel machines so as to minimize the total weighted completion time of jobs.Whereas the best previously known approximation algorithms for this problem are based on LP relaxations, we give a 32–approximation algorithm that relies on a convex quadratic programming relaxation. For the special case of two machines we present a further improvement to a 1.2752–approximation; we introduce a more sophisticated semidefinite programming relaxation and apply the random hyperplane technique introduced by Goemans and Williams on for the MAXCUT problem and its refined version of Feige and Goemans. To the best of our knowledge, this is the first time that convex and semidefinite programming techniques (apart from LPs) are used in the area of scheduling.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15882
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14655
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherapproximation algorithmen
dc.subject.otherrandomized algorithmen
dc.subject.otherconvex quadratic programen
dc.subject.othersemidefinite programmingen
dc.subject.otherschedulingen
dc.titleSemidefinite Relaxations for Parallel Machine Schedulingen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber1998, 577en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.subject.msc200090C27 Combinatorial optimizationen
tub.subject.msc200068Q25 Analysis of algorithms and problem complexityen
tub.subject.msc200090B35 Scheduling theory, deterministicen
tub.subject.msc200068M20 Performance evaluation; queueing; schedulingen
tub.subject.msc200090C20 Quadratic programmingen
tub.subject.msc200090C22 Semidefinite programmingen
tub.subject.msc200090C25 Convex programmingen

Files

Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-577-1998.pdf
Size:
136.05 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
Report-577-1998.ps.gz
Size:
59.42 KB
Format:
Unknown data format

Collections