Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Convex quadratic and semidefinite programming relaxations in Scheduling
Author(s): Skutella, Martin
Type: Research Paper
Abstract: We consider the problem of scheduling unrelated parallel machines subject to release dates so as to minimize the total weighted completion time of jobs. The main contribution of this paper is a provably good convex quadratic programming relaxation of strongly polynomial size for this problem. The best previously known approximation algorithms are based on LP relaxations in time- or interval-indexed variables. Those LP relaxations, however, suffer from a huge number of variables. As a result of the convex quadratic programming approach we can give a very simple and easy to analyze 2-approximation algorithm which can be further improved to performance guarantee 3/2 in the absence of release dates. We also consider preemptive scheduling problems and derive approximation algorithms and results on the power of preemption which improve upon the best previously known results for these settings. Finally, for the special case of two machines we introduce a more sophisticated semidefinite programming relaxation and apply the random hyperplane technique introduced by Goemans and Williamson for the MaxCut problem; this leads to an improved 1.2752-approximation.
Subject(s): approximation algorithms
convex optimization
performance guarantee
randomized algorithms
scheduling theory
unrelated machines
worst-case ratio
Issue Date: 2000
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
90C59 Approximation methods and heuristics
90C20 Quadratic programming
90C25 Convex programming
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2000, 683
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: 31.73 MB
DownloadShow Preview
Format: Unknown | Size: 163.89 kB

Item Export Bar

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