Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Semidefinite Relaxations for Parallel Machine Scheduling
Author(s): Skutella, Martin
Type: Research Paper
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.
Subject(s): approximation algorithm
randomized algorithm
convex quadratic program
semidefinite programming
Issue Date: 1998
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90C27 Combinatorial optimization
68Q25 Analysis of algorithms and problem complexity
90B35 Scheduling theory, deterministic
68M20 Performance evaluation; queueing; scheduling
90C20 Quadratic programming
90C22 Semidefinite programming
90C25 Convex programming
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 1998, 577
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 136.05 kB
DownloadShow Preview
Format: Unknown | Size: 59.42 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.