Title
Convex quadratic and semidefinite programming relaxations
in Scheduling
Author
-
Publication
Journal of the Association for Computing Machinery 48(2), 206-242, 2001.
Source
-
Classification
-
| MSC: |
| primary: | 90C27 | Combinatorial optimization |
| secondary: | 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 |
Keywords
-
Approximation algorithms, convex optimization,
performance guarantee, randomized algorithms, scheduling theory,
unrelated machines, worst-case ratio
-
-
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.
See also
-
