Semidefinite Relaxations for Parallel Machine Scheduling
dc.contributor.author | Skutella, Martin | |
dc.date.accessioned | 2021-12-17T10:14:40Z | |
dc.date.available | 2021-12-17T10:14:40Z | |
dc.date.issued | 1998 | |
dc.description.abstract | We 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.issn | 2197-8085 | |
dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15882 | |
dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14655 | |
dc.language.iso | en | en |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
dc.subject.ddc | 510 Mathematik | en |
dc.subject.other | approximation algorithm | en |
dc.subject.other | randomized algorithm | en |
dc.subject.other | convex quadratic program | en |
dc.subject.other | semidefinite programming | en |
dc.subject.other | scheduling | en |
dc.title | Semidefinite Relaxations for Parallel Machine Scheduling | en |
dc.type | Research Paper | en |
dc.type.version | submittedVersion | en |
tub.accessrights.dnb | free | en |
tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
tub.affiliation.institute | Inst. Mathematik | de |
tub.publisher.universityorinstitution | Technische Universität Berlin | en |
tub.series.issuenumber | 1998, 577 | en |
tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
tub.subject.msc2000 | 90C27 Combinatorial optimization | en |
tub.subject.msc2000 | 68Q25 Analysis of algorithms and problem complexity | en |
tub.subject.msc2000 | 90B35 Scheduling theory, deterministic | en |
tub.subject.msc2000 | 68M20 Performance evaluation; queueing; scheduling | en |
tub.subject.msc2000 | 90C20 Quadratic programming | en |
tub.subject.msc2000 | 90C22 Semidefinite programming | en |
tub.subject.msc2000 | 90C25 Convex programming | en |