Semidefinite Relaxations for Parallel Machine Scheduling
Martin Skutella
Fachbereich Mathematik, MA 6–1
Technische Universität Berlin
Straße des 17. Juni 136
D–10623 Berlin, Germany
Abstract
Weconsidertheproblemofschedulingunrelatedparallel
machines so as to minimize the total weighted completion
time of jobs. Whereas the best previously known approxi-
mation algorithms for this problem are based on LP relax-
ations, we give a 3
2–approximation algorithm that relies on
a convex quadratic programming relaxation. For the spe-
cial case of two machineswe present a further improvement
to a 1
2752–approximation; we introduce a more sophis-
ticated semidefinite programming relaxation and apply the
random hyperplane technique introduced by Goemans and
Williamson for the MAXCUT problem and its refined ver-
sion of Feige and Goemans. To the best of our knowledge,
this is the first time that convex and semidefinite program-
ming techniques (apart from LPs) are used in the area of
scheduling.
1 Introduction
The last years have witnessed a very fast development in
the area of approximation algorithms for NP-hard schedul-
ing problems. Apart from purely combinatorialapproaches,
linear programming (LP) relaxations have been proved to
be a useful tool in the design and analysis of approximation
algorithms for several machine scheduling problems, see,
e.g., [27, 43, 33, 20, 40, 39, 19, 4, 34, 29, 10, 6, 42, 41, 14,
38, 31, 13, 44].
In this paper we pursue a somewhat different line of re-
search. We develop approximation algorithms that are not
based on polyhedral relaxations but on convex quadratic
programmingrelaxations whichhave neverbeen used in the
Copyright 1998 IEEE. Published in the Proceedings of FOCS’98, 8-11
November 1998 in Palo Alto, CA. Personal use of this material is permit-
ted. However, permission to reprint/republish this material for advertising
or promotional purposes or for creating new collective works for resale or
redistribution to servers or lists, or to reuse any copyrighted component of
this work in other works, must be obtained from the IEEE. Contact: Man-
ager, Copyrights and Permissions / IEEE Service Center / 445 Hoes Lane
/ P.O. Box 1331 / Piscataway, NJ 08855-1331, USA. Telephone: + Intl.
732-562-3966.
area of scheduling before. Convex and more specifically
semidefinite programming relaxations of combinatorial op-
timization problems have attracted the attention of many re-
searchers [11]. Grötschel, Lovász, and Schrijver [17] used
semidefinite programming to design a polynomial-time al-
gorithm for finding the largest stable set in a perfect graph.
The use of semidefinite relaxations in the design of ap-
proximation algorithms was pioneered by Goemans and
Williamson [15] for the problems MAXCUT, MAXDICUT,
and MAX2SAT.
In semidefinite programming, one minimizes a linear
functionsubject to linear constraints and the additional con-
straint that certain matrices whose entries are affine lin-
ear functions in the variables of the program are positive
semidefinite. Since the subset of all positive semidefinite
matrices constitutes a cone in
n
n, semidefinite programs
form a special class of convex programs. Under some re-
quirements on the feasible space, they can be solved within
an additive error of εin polynomial time for any given
ε
0, cf. [18]. Practical efficiency can be obtained through
interior point methods, see, e.g., [1]. More information
on semidefinite programming can for example be found in
[47].
Goemans and Williamson [15] formulated the problems
MAXCUT and MAXDICUT as integer quadratic programs
in
1
1
–variables and considered a relaxation to a vec-
tor program which is equivalent to a semidefinite program.
They introduced the idea of rounding a solution to this re-
laxation to a feasible cut with a randomhyperplane through
the origin. Their analysis is based on the observation that
the probability for an edge to lie in the (directed) cut can
be bounded from below in terms of the corresponding co-
efficient in the vector program. This leads to performance
ratios 0
878 and 0
796 for MAXCUT and MAXDICUT, re-
spectively.
Feige and Goemans [8] refined this approach by adding
additional constraints to the vector program and by mod-
ifying its solution before applying the random hyperplane
technique. Thisleadsto animprovementinthe performance
guarantee from 0
796 to 0
859 for MAXDICUT. More ap-
plications of semidefinite programming relaxations in the
design of approximation algorithms can for instance be
found in [22, 5, 9, 46].
We contribute to this line of research: The only prob-
lems in combinatorial optimization where the random hy-
perplane technique discussed above has proved useful in
the design of approximation algorithms so far are maxi-
mization problems, see also [9, 46]. The reason is that up
to now only lower bounds on the crucial probabilities in-
volved have been attained, see [15, Lemmas 3.2 and 3.4;
Lemmas 7.3.1 and 7.3.2]. Inspired by the work of Feige
and Goemanswe analyzea slightly modifiedroundingtech-
nique and prove upper bounds for those probabilities. To-
gether with a more sophisticated semidefinite programming
relaxationthis leads to the first approximationalgorithm for
a minimization problem that is based on the random hyper-
plane approach.
We consider the following scheduling problem. We are
given a set of njobs J
1
n
and mparallel machines
or processors. Each job jhas a positive integral processing
requirement pij which depends on the machine ijob jwill
be processed on. Each job jmust be processed for the re-
spective amountof time on one ofthe mmachines, and may
be assigned to any of them. Every machine can process at
most one job at a time. The completion time of job jin
a schedule is denoted by Cj. We aim to minimize the to-
tal weighted completion time ∑j
JwjCjwhere wjdenotes
a given nonnegativeintegral weight of job jwhich is a mea-
sure for its importance. In the standard notation of Graham
et al. [16], this problem reads R
∑wjCj. It is shown to be
NP-hard in [3, 26], even for a fixed numberm
2 of identi-
cal parallel machines. The special case of identical parallel
machines, i.e., for each job jand all machines iwe have
pij
pj, is denoted by P
∑wjCj.
The corresponding single machine scheduling problem
can be solved in polynomial time using Smith’s Ratio Rule
[45]: Sequence the jobs in order of nonincreasing ratios
wj
pj. Therefore the only problem in constructing good
schedules for instances of R
∑wjCjis to assign the jobs
appropriately to machines. Afterwards one sequences all
jobs that have been assigned to machine iin order of non-
increasing ratios wj
pij. Thus, whenever we talk about
an assignment of jobs to machines we associate a corre-
sponding schedule. We will always assume that whenever
wk
pik
wj
pij for a pair of jobs j
kand both jobs are as-
signed to machine ithe job with smaller index is scheduled
first. For each machine i
1
mwe definea correspond-
ing total order
J
i
on the set of jobs by setting j
ikif
either wj
pij
wk
pik or wj
pij
wk
pik and j
k. For
the special case of identical parallel machines we always
assume that the jobs are indexed such that 1
2
n.
The first approximation result for minimizing the total
weighted completion time on unrelated parallel machines
was given by Phillips, Stein, and Wein [32] and achieves
performance ratio O
log2n
. Hall, Schulz, Shmoys, and
Wein [19] presented a 16
3–approximation algorithm that is
based on an LP relaxation in time-indexed variables and
uses the rounding technique of Shmoys and Tardos for the
generalized assignment problem [43]. This result was suc-
cessively improved by Schulz and Skutella to performance
ratios 2
εand 3
2
ε[42, 41]. The
3
2
ε
–approximation
algorithm is also the best known result if the numberof ma-
chines is fixed to m
2. However, for the special case
of identical parallel machines Kawaguchi and Kyan [23]
showed that list scheduling in order of nonincreasing ratios
wj
pjis a 1
21–approximation algorithm. For any fixed
number of identical parallel machines Sahni [37] gave a
polynomial time approximation scheme which builds upon
a general dynamic programming technique of Rothkopf
[36] and Lawler and Moore [25]. It was observedby Woeg-
inger [48] that the result of Sahni can be extended to a fixed
number of uniform parallel machines which run at different
but not job-dependent speeds.
In thispaperwe introducea new technique. We start with
aformulationof R
∑wjCjas anintegerquadraticprogram
in Section 2, consider its continuous relaxation, and discuss
a simple randomized rounding heuristic. In Section 3 we
describe how the objective function of the quadratic pro-
gram can be convexified yielding a convex programming
relaxation that can be solved in polynomial time. Together
with randomized rounding this leads to an approximation
algorithm with performance guarantee 3
2which is an ε–
improvement on the previously best known result. In Sec-
tion 4 we present a more sophisticated vector programming
relaxation for the special case of two machines. We show
that a modification of the random hyperplane approach of
Goemans and Williamson leads to a 1
339–approximation
algorithm for R2
∑wjCj. A combination of this algo-
rithm with the 3
2–approximation leads to an improved per-
formanceguarantee1
276. In Section5 wediscuss relations
between MAXCUT and scheduling on identical parallel ma-
chines. In particular, we present an approximation preserv-
ing reduction of Pm
∑wjCjto MAXkCUT where k
m.
Throughout the paper we will use the following conven-
tion: The value of an optimum solution to the scheduling
problem under consideration is denoted by Z
. For a relax-
ation
R
we denote the optimumvalue of
R
by Z
Rand the
value of an arbitrary feasible solution ato
R
by ZR
a
. In
this extended abstract we omit some details and proofs for
reasons of brevity. A more detailed version can be found in
[44, Chapter 3].
2 Quadratic programming formulations
The problemof schedulinga set of jobs on unrelatedpar-
allel machines can be formulated as an integer quadratic
program in assignment variables. We introduce for each
machine i
1
mand each job j
Ja binary variable
aij
0
1
which is set to 1 if and only if job jis being
processed on machine i. Lenstra, Shmoys, and Tardos [27]
used the same variables to formulate the problem of mini-
mizing the makespan of unrelated parallel machines as an
integer linear program. However, minimizing the average
weighted completion time forces quadratic terms and leads
to the following program
IQP
:
min ∑
j
JwjCj
s. t. m
∑
i
1
aij
1 for j
J(1)
Cj
m
∑
i
1
aij
pij
∑
k
ij
aik
pik
for j
J(2)
aij
0
1
for all i
j(3)
Constraints (1) ensure that each job is assigned to exactly
one of the mmachines. If job jhas been assigned to ma-
chine i, its completion time is the sum of its own processing
time pij and the processing times of other jobs k
ijthat
are also scheduled on machine i. The right hand side of
(2) is the sum of these expressions over all the machines i
weighted by aij. It is thus equal to the completion time of
j. Notice that we could remove constraints (2) and replace
Cjin the objective function by the right hand side of (2).
We denote the relaxation of
IQP
that we get by relax-
ing the integrality conditions (3) to aij
0, for all i
j, by
QP
. A feasible solution ¯ato
QP
can be turned into a
feasible solution to
IQP
, i.e., a feasible schedule, by ran-
domized rounding: Each job jis assigned independently
at random to one of the machines with probabilities given
through the values ¯aij; notice that ∑m
i
1¯aij
1 by (1). We
refer to this rounding technique as Algorithm RANDOM-
IZED ROUNDING. A similar algorithm, however based on
a time-indexed LP relaxation, has been studied by Schulz
and Skutella [41]. The idea of using randomized rounding
in the study of approximationalgorithms was introduced by
Raghavanand Thompson [35], an overviewcan be found in
[30].
Theorem 2.1. Given a feasible solution ¯a to
QP
, the ex-
pected value of the schedule computed by Algorithm RAN-
DOMIZED ROUNDING is equal to ZQP
¯a
.
The proof of Theorem2.1 relies on the followinglemma
whose proof is straightforward and therefore omitted for
reasons of brevity.
Lemma 2.2. Consider an algorithm that assigns each job
j randomly to one of the m machines. Then, the expected
completion time of job j is given by
E
Cj
m
∑
i
1
Pr
j
i
pij
∑
k
ij
Pr
j
k
i
pik
where “j
k
i” (“j
i”) denotes the event that both jobs
j and k (job j) are assigned to machine i.
Proof of Theorem 2.1. Since for each machine iand each
pair of jobs j
kthe random variables aij and aik are drawn
independentlyfrom each otherin Algorithm RANDOMIZED
ROUNDING, we get
Pr
j
k
i
Pr
j
i
Pr
k
i
¯aij
¯aik
Lemma 2.2 yields the result by constraints (2) and linearity
of expectations.
Algorithm RANDOMIZED ROUNDING can easily be de-
randomized by the method of conditional probabilities.
We refer to its derandomized version as DERANDOM-
IZED ROUNDING. IfAlgorithmRANDOMIZED ROUNDING
starts with an optimum solution to
QP
, it computes an in-
tegral solution the expected value of which is equal to the
optimum value Z
QP by Theorem 2.1. Thus there must ex-
ist at least one random choice that yields a schedule whose
value is bounded from above by Z
QP. On the other hand we
know that each feasible solution to
IQP
is by definition
also feasible for
QP
. This yields the following theorem:
Theorem 2.3. The optimal values of
IQP
and
QP
are
equal. Moreover, given an optimum solution ¯a to
QP
one
can construct an optimum solution to
IQP
by assigning
each job j to an arbitrary machine i with ¯aij
0.
Bertsimas, Teo, and Vohra [2] used similar techniques to
establish the integrality of several polyhedra.
It follows from Theorem 2.3 that it is still NP-hard to
find an optimum solution to the quadratic program
QP
. In
the followingtwo sections we considerrelaxations of
IQP
that can be solved in polynomial time. The idea of the first
relaxation is to convexify the objective function of
QP
in
order to get a convex quadratic program. The second relax-
ation is a semidefinite programmingrelaxation of
IQP
for
the special case of two machines which extends the ideas
used in [15] and [8] for MAX2SAT and MAXDICUT.
3 A convex quadratic programming relax-
ation
The quadratic program
QP
can be rewritten as
min cTa
1
2aTDa (4)
s. t. m
∑
i
1aij
1 for j
J
a
0
where a
mn denotes the vector consisting of all variables
aij lexicographically ordered with respect to the natural or-
der 1
2
mof the machines and then, for each machine
i, the jobs ordered according to
i. The vector c
mn
is given by cij
wjpij and D
d
ij
hk
is a symmetric
mn
mn–matrixgiven through
d
ij
hk
0 if i
hor j
k,
wjpik if i
hand k
ij,
wkpij if i
hand j
ik.
Because of the lexicographicorder of the indices the matrix
Dis decomposed into mdiagonal blocks Di,i
1
m,
correspondingtothemmachines. If weassumethat thejobs
are indexed according to
iand if we denote pij simply by
pj, the i–th block Dihas the following form:
Di
0w2p1w3p1
wnp1
w2p10w3p2
wnp2
w3p1w3p20wnp3
.
.
..
.
.....
.
.
wnp1wnp2wnp3
0
(5)
Consider an instance consisting of 2 jobs where all weights
and processing times on the i–th machine are equal to one.
In this case we get
Di
0 1
1 0
; (6)
in particular, detDi
1 and Dis not positive semidefinite.
It is well known that the objective function (4) is convex if
and only if the matrix Dis positive semidefinite. Moreover,
a convex quadratic program of the form mincTx
1
2xTDx
subject to Ax
b,x
0, can be solved in polynomial time
(see, e.g., [24, 7]). Thus we get a polynomially solvable
relaxation of
QP
if we manage to convexify its objective
function. The rough idea is to raise the diagonal entries of
Dabove 0 until Dis positive semidefinite.
For binary vectors a
0
1
mn we can rewrite the linear
term cTain (4) as aTdiag
c
a, where diag
c
denotes the
diagonal matrix whose diagonal entries coincide with the
entries of c. We try to convexify the objective function of
QP
by adding a positive fraction 2γ
diag
c
, 0
γ
1,
to Dsuch that D
2γ
diag
c
is positive semidefinite. This
leads to the following modified objective function:
min
1
γ
cTa
1
2aT
D
2γ
diag
c
a(7)
Since c
0, the value of the linear function cTais
greater than or equal to the value of the quadratic func-
tion aTdiag
c
afor arbitrary a
0
1
mn; equality holds for
a
0
1
mn. Therefore the modified objective function (7)
underestimates (4). Since we want to keep the gap as small
as possible and since (7) is nonincreasing in γfor each fixed
vector a, we are looking for a smallest possible value of γ
such that D
2γ
diag
c
is positive semidefinite.
Lemma 3.1. The function
a
1
γ
cTa
1
2aT
D
2γ
diag
c
a
is convex for arbitrary instances of R
∑wjCjif and only
if γ
1
2.
Proof. In order to show that the positive semidefiniteness
of D
2γ
diag
c
for arbitrary instances implies γ
1
2, we
considertheexamplegivenin(6). Here,thediagonalentries
of the i–th block of D
2γ
diag
c
are equal to 2γsuch
that this block is positive semidefinite if and only if γ
1
2.
Thus, we consider the case γ
1
2and show that D
diag
c
is positive semidefinite for arbitrary instances. Using the
same notation as in (5) the i–th block of D
diag
c
has the
form
A
w1p1w2p1w3p1
wnp1
w2p1w2p2w3p2
wnp2
w3p1w3p2w3p3
wnp3
.
.
..
.
..
.
.....
.
.
wnp1wnp2wnp3
wnpn
(8)
An easy calculation shows that the matrix Ais positive
semidefinite since w1
p1
wn
pn.
Since for γ
1
2the matrix D
2γ
diag
c
is the sum
of the two positive semidefinite matrices D
diag
c
and
2γ
1
diag
c
, the result follows.
Lemma 3.1 and the remarks above motivate the consid-
eration of the following convex quadratic programming re-
laxation
CQP
:
min 1
2cTa
1
2aT
D
diag
c
a
s. t. m
∑
i
1aij
1 for j
J(9)
a
0 (10)
As mentionedabove
CQP
can be solved in polynomial
time. If we consider the special case of identical parallel
machines P
∑wjCj, we can directly give a Karush-Kuhn-
Tucker point and therefore an optimum solution to
CQP
.
The following result can be proved by a simple symmetry
argument. We omit the proof for reasons of brevity.
Lemma 3.2. For instances of P
∑wjCjthe vector ¯a with
¯aij
1
m, for all i
j, is an optimum solution to
CQP
. This
optimum solution is unique if all ratios wj
pj, j
1
n,
are different and positive.
Theorem 3.3.
a) Computing an optimum solution ¯a to
CQP
and us-
ing RANDOMIZED ROUNDING to construct a fea-
sible schedule is a 2–approximation algorithm for
R
∑wjCj.
b) Assigning each job independently and uniformly at
random to one of the m machines is a
3
2
1
2m
–
approximation algorithm for P
∑wjCj.
Proof. Notice that the algorithm described in part b) coin-
cides with the algorithm of part a) for the optimum solution
¯ato
CQP
given in Lemma 3.2. Theorem 2.1 yields
E
∑
jwjCj
ZCQP
¯a
1
2
cT¯a
¯aTdiag
c
¯a
2
ZCQP
¯a
2
Z
CQP
The inequality follows from ZCQP
¯a
1
2cT¯aand
¯aTdiag
c
¯a
0. Since ¯acan be computed in polynomial
time and Z
CQP is a lower bound on Z
, we have found a
2–approximationalgorithm.
To prove part b) we use a second lower bound on Z
.
For the case of identical parallel machines constraints (9)
imply cTa
∑jwjpj
Z
for every feasible solution ato
CQP
. Since ¯aTdiag
c
¯a
1
mcT¯a, the same arguments as
above yield E
∑jwjCj
3
2
1
2m
Z
.
It also follows from Theorem 3.3 that
CQP
is a 2–
relaxation, i.e., Z
2
Z
CQP. This bound is tight even for
thecaseofidenticalparallelmachines. Consideraninstance
with onejob ofsize and weightone suchthat the value Z
of
an optimum schedule is equal to one. By Lemma 3.2 we get
Z
CQP
m
1
2m. Thus, if mgoes to infinity the ratio Z
Z
CQP
converges to two.
Unfortunately, we cannot directly carry over the 3
2–
approximationto the setting of unrelated parallel machines.
The reason is that cTais not necessarily a lower bound on
Z
for every feasible solution ato
CQP
. However, the
value of each binary solution ais bounded from below by
cTa. The idea for an improved approximation result is to
add this lower bound as a constraint to
CQP
. In the con-
text of LP based approximations, the second part of Theo-
rem 3.3 and a similar idea has been given in [41]. It leads
to the following strengthened relaxation
CQP
, which is
a convex program and can therefore be solved through the
ellipsoid algorithm within any additive error ε
0 in poly-
nomial time, see [18].
min ZCQP
s. t. m
∑
i
1aij
1 for j
J
ZCQP
1
2cTa
1
2aT
D
diag
c
a(11)
ZCQP
cTa(12)
a
0
We show that
CQP
is actually equivalentto a semidef-
inite program.
Lemma 3.4. There exists a symmetric mn
mn–matrix
M
Z
a
which can be computed in polynomial time and
whose entries are linear functions in the variables Z and
aij, such that
Z
1
2cTa
1
2aT
D
diag
c
a
if and only if M
Z
a
is positive semidefinite. In particular,
CQP
can be interpreted as a semidefinite program.
Sketch of proof. As proposed in [47, Section 2] we define
M
Z
a
Emn
1Ba
Ba
T2Z
cTa
where Emn
1denotes the
mn
1
–dimensional identity
matrix and the matrix Bis defined by the Cholesky decom-
position
D
diag
c
BTB. An easy calculation yields
the result.
The next lemma follows from the proof of Theorem 3.3
and constraint (12).
Lemma 3.5. Given a feasible solution ¯a to
CQP
Al-
gorithm RANDOMIZED ROUNDING computes a sched-
ule whose expected value is bounded from above by 3
2
ZCQP
¯a
.
Lemma 3.5 yields that
CQP
is a 3
2–relaxation for
R
∑wjCj. We get a randomizedapproximation algorithm
with expected performance guarantee 3
2
εif we apply Al-
gorithm RANDOMIZED ROUNDING to an almost optimal
solution to
CQP
which can be computed in polynomial
time. We can prove a slightly better bound for the deran-
domized version.
Theorem 3.6. Computing a near optimal solution to
CQP
and using Algorithm DERANDOMIZED ROUNDING
to get a feasible schedule is a 3
2–approximation algorithm
for R
∑wjCj.
Proof. We compute a feasible solution ¯ato
CQP
satisfy-
ing ZCQP
¯a
Z
CQP
1
3. By Lemma 3.5 Algorithm DE-
RANDOMIZED ROUNDING convertsthis solutioninto a fea-
sible schedule whose value is bounded by 3
2
ZCQP
¯a
3
2
Z
CQP
1
2
3
2
Z
1
2. Since all the weights and pro-
cessing times are integral, the same holds for Z
. The value
of our schedule can therefore be bounded by 3
2
Z
.
The performance ratios given in Lemma 3.5 and Theo-
rem 3.6 are only tight if (12) is tight for the solution ¯ato
CQP
. In general, if ZCQP
¯a
is much larger than cT¯a, we
get a better performance ratio (see Figure 2 below).
Corollary 3.7. For any feasible solution ¯a to
CQP
Al-
gorithm RANDOMIZED ROUNDING computes a feasible
schedule whose expected value is bounded from above by
1
cT¯a
2ZCQP
¯a
ZCQP
¯a
.
Approximation algorithms with the same or slightly
worse performance ratios than those presented in Theo-
rems 3.3 and 3.6 have already been given by Schulz and
Skutella [42, 41]. In contrast to our approachhere they used
LP relaxations in time-indexed variables together with ran-
domizedrounding. However,theunderlyingintuitionof our
quadratic programs and their LPs is similar.
4 A semidefinite relaxation for two machines
In this section we consider the problem of scheduling
two unrelated parallel machines which is usually denoted
by R2
∑wjCj. To keep the notation as simple as possible
we assume that the two machines are numbered 0 and
1
throughout this section.
We start with a reformulation of
IQP
in variables
xj
1
1
, for j
J, and additional variables x0
x
1
1
1
with x
1
x0; job jis being assigned to machine
0 if xj
x0and to machine
1 otherwise. Thereforethe as-
signment variables aij in
IQP
are replaced by 1
xixj
2and
the quadratic terms aijaik by xjxk
xixj
xixk
1
4. Note that we
have introduced the variable x
1only to keep notation sim-
ple; it couldas well be replacedby
x0. We get a relaxation
of
IQP
to a vector program
VP
if we replace the one-
dimensional variables xjwith absolute value 1 by vectors
vj
n
1of unit length.
min ∑
jwjCj
s. t. Cj
0
∑
i
1
1
vivj
2
pij
∑
k
ij
vjvk
vivj
vivk
1
4
pik
(13)
v
1v0
1
vjvj
1 for j
J
0
1
Here vjvkdenotes the scalar product of the vectors vjand
vk. It is well known that such a program is equivalent to
a semidefinite program in variables corresponding to the
scalar products (see, e.g., [15]). This program can be
strengthened by adding the constraints
vjvk
vivj
vivk
1
0 (14)
for i
0
1
and j
k
J. Constraints of the same form
have been used by Feige and Goemans [8] to improvesome
of the approximation results of Goemans and Williamson
[15].
It is one of the key insights of this paper that the vec-
tor program can be further strengthened with the quadratic
constraint (11) from the convexquadratic program
CQP
.
For a feasible solution vto
VP
we denote by a
a
v
the
correspondingsolution to
CQP
, i.e., aij
1
vivj
2, and add
the constraint
∑
jwjCj
1
2cTa
1
2aT
D
diag
c
a(15)
∑
jwj
0
∑
i
1
aij
1
aij
2pij
∑
k
ij
aik
pik
to the vectorprogram
VP
. The resulting program with the
additional constraints (14) and (15) is denoted by
SDP
.
Note that constraint (12) is included in (13) and (14).
By Lemma3.4andour remarkabove
SDP
canbeinter-
preted as a semidefinite programin variables corresponding
to the scalar products vjvk. For a feasible solution to
SDP
we consider the random hyperplane rounding of Goemans
and Williamson:
Algorithm RANDOM HYPERPLANE
1) Draw a vector rrandomly and uniformly distributed
from the unit-sphere of
n
1.
2) For each job j, assign jto the machineiwith sgn
vjr
sgn
vir
.
In the second step ties can be broken arbitrarily; they occur
with probability zero. The random vector rcan be inter-
preted as the normal vector of a random hyperplanethrough
the origin which partitions the set of vectors vj,j
J, and
therefore the jobs into two sets. In contrast to Algorithm
RANDOMIZED ROUNDING jobs are no longer assigned in-
dependently to the machines, but the hyperplane induces a
correlation between the random decisions.
To analyze
SDP
and Algorithm RANDOM HYPER-
PLANE we need the followinglemma whichis a restatement
of [15, Lemma 3.2 and Lemma 7.3.1]. For given vectors
vj
vk,j
k
J
0
1
, we denote the enclosed angle by
αjk.
Lemma 4.1. For j
k
J, i
0
1
, and for given unit
vectors vi
vj
vk, Algorithm RANDOM HYPERPLANE yields
the following probabilities:
a) Pr
j
i
1
αij
π.
b) Pr
j
k
i
1
αjk
αij
αik
2π.
As a result of Lemma 2.2 and Lemma 4.1 the expected
value of the completion time of job jin the schedule com-
puted by Algorithm RANDOM HYPERPLANE is given by
E
Cj
0
∑
i
1
1
αij
π
pij
∑
k
ij
1
αjk
αij
αik
2π
pik
(16)
We want to compare the expected value of the schedule
computed by Algorithm RANDOM HYPERPLANE to the
value of the feasible solution to
SDP
we started with.
Lemma 4.2. Let v and a
a
v
be a feasible solution to
SDP
with value Z and consider a random assignment of
jobs to machines satisfying
Pr
j
i
ρ1
2
1
vivj
2
1
aij
2
aij
and
Pr
j
k
i
ρ2
2
vjvk
vivj
vivk
1
4
aijaik
for i
0
1
, j
k
J, and for certain parameters 1
ρ1
ρ2. Then the expected value of the computed schedule
is bounded from above by
ρ13cTa
4
ρ2
Z
3cTa
4
ρ2
Z
Sketch of proof. Observe that the required bounds in
Lemma 4.2 compare the given probabilities to the average
of the corresponding coefficients in (13) and (15). It there-
fore follows from Lemma 2.2, linearity of expectations, and
an easy calculation that the expected value of the computed
schedule is boundedby max
ρ1
ρ2
Z
ρ2
Z. A preciser
analysis yields the stronger bound given in the lemma.
Inspired by the work of Feige and Goemans [8] we give
a rounding scheme that fulfills the conditions described in
Lemma 4.2 for ρ1
1
1847 and ρ2
1
3388. We apply Al-
gorithm RANDOM HYPERPLANE to a set of modified vec-
tors uj,j
J, which are constructed from the vectors vjby
taking advantage of the special role of v0and v
1. For each
job j
Jthe vectors v0,vj, and ujare linearly dependent,
i.e., ujis coplanar with v0and vj. Moreover, ujlies on the
same side of the hyperplane orthogonal to v0as vjand its
distance to this hyperplane is increased compared to vj. In
other words, ujis attained by moving vjtowards the nearer
of the two points v0and v
1, see Figure 1.
We describe this mapping of vjto ujby a function f:
0
π
0
π
where f
αij
equals the angle formed by uj
and vifor i
0
1
. In particular, fhas the property that
f
π
θ
π
f
θ
such that both machines are treated
in the same manner. In order to compute the probability
Pr
j
k
i
for Algorithm RANDOM HYPERPLANE based
on the modified vectors ujand uk, we need to know the
angle between ujand ukfor two jobs j
k
J. This angle
is implicitly given by the cosine rule for spherical triangles,
see [8].
If we use the function f1
θ
:
π
2
1
cos
θ
proposed
by Feige and Goemans we get
Pr
j
i
1
cos
αij
2
1
vivj
2
aij
f
α0j
v
1
uk
vk
f
α
1
k
α
1
k
α0j
uj
vj
ϕjk
v0
Figure 1. Modification according to the func-
tion f.
for each job j. In other words, the probability that a job is
assigned to a machine is equal to the corresponding coeffi-
cient in (13). On the other hand, the function f1does not
yield a possibility to boundthe probabilities Pr
j
k
i
for
j
k
Jin terms of the corresponding coefficients in (13)
and (15).
Therefore we use a different function f2defined by
f2
θ
f1
ξ
θ
where ξ
θ
min
π
max
0
π
2
1
3662
θ
π
2
. This yields a rounding scheme with expected
performance guarantee 1
3388. We have shown numer-
ically that the conditions in Lemma 4.2 are fulfilled for
ρ1
1
1847 and ρ2
1
3388 in this case. As proposed
by Feige and Goemans this was done by discretizing the
set of all possible angles between three vectors and test-
ing for each triple the validity of the bounds for the given
parameters ρ1and ρ2which are nearly tight. We should
mention that both constraints (14) and (15) are crucial for
our analysis. In the absence of one of these constraints one
can construct constellations of vectors such that no constant
worst case boundsρ1and ρ2exist for our analysis. We omit
details for reasons of brevity.
Theorem 4.3. Computing an almost optimal solution to
SDP
, modifying it according to f2, and using Algorithm
RANDOM HYPERPLANE to construct a feasible schedule
yields arandomizedapproximationalgorithmwith expected
performance guarantee 1
3388.
It was shown in [28] that Algorithm RANDOM HYPER-
PLANE can be derandomized. We get a deterministic ver-
sion of our approximation algorithm if we make use of
the derandomized version of Algorithm RANDOM HYPER-
PLANE.
We strongly believe that there exists a function similar
to f2which yields an expected performance guarantee of
4
3. On the other hand we can show that this value is best
possible for our kind of analysis. Consider the constel-
lation α0j
α0k
π
2and αjk
0. The symmetry of f
yields f
π
2
π
2such that uj
uk
vj
vk. Therefore
Pr
j
k
0
1
2and the right hand side of the correspond-
ing inequality in Lemma 4.2 is equal to 3
8ρ2. We have also
tried to bound the probabilities by a different convex com-
bination of the corresponding coefficients in (13) and (15)
ratherthan using their averageas in Lemma 4.2; but this did
not lead to any improvement.
We can also apply Algorithm RANDOMIZED ROUND-
ING to turn a feasible solution a
a
v
to
SDP
into a
provably good schedule. Although the worst case ratio of
this algorithm is worse than the performance ratio of the
rounding scheme based on Algorithm RANDOM HYPER-
PLANE, a combinationof the two roundingtechniques leads
to a further improvement in the performance guarantee.
Theorem 4.4. For an almost optimal solution to
SDP
,
either Algorithm RANDOMIZED ROUNDING or Algorithm
RANDOM HYPERPLANE (together with f2) produces a
schedule whose expected value is bounded by 1
2752
Z
.
Sketch of Proof. Notice that by Corollary 3.7 and
Lemma 4.2 the two rounding techniques do not be-
have bad for the same class of instances and solutions to
SDP
, see Figure 2.
1
3388
1
5
1
1
2752
performance ratio
1
2233
0 0
5504 1
RANDOM HYPERPLANE
RANDOMIZED ROUNDING
cTa
v
ZSDP
v
Figure 2. Comparison of Randomized Round-
ing and Random Hyperplane.
Observations of this type have alreadybeen used in other
contexts to get improved approximation results. Theo-
rem 4.4 also implies that
SDP
is a 1
2752–relaxation for
R2
∑wjCj.
Up to now, the combination of semidefinite relaxations
like the one we are discussing here and the rounding
technique of Algorithm RANDOM HYPERPLANE has only
proved useful for approximations in the context of maxi-
mization problems [15, 8, 9, 46]. In contrast to our consid-
erations, in the analysis of these results one needs a good
lower bound on the probabilities for the assignments in Al-
gorithm RANDOM HYPERPLANE. However, it seems to be
much harder to attain good upper bounds. Our main contri-
bution to this problem is the additional quadratic cut (15).
We hope that this approach will also prove useful for other
problems in combinatorial optimization.
5 MaxCut algorithms for scheduling identi-
cal parallel machines
We associate with each instance of P
∑wjCja com-
plete undirected graph GJon the set of vertices Jtogether
with weights on the set of edges EJgiven by c
jk
wjpk
for j
k
J,k
j. Each partition of the set of vertices Jof
GJinto msubsets J1
Jmcan be interpretedas a machine
assignment and corresponds to a feasible schedule. More-
over, thevalueof a schedulecan beinterpretedas the weight
of the set Esch formed by those edges in EJwith both end-
points in the same subset plus the constant term ∑jwjpj.
The remaining edges in Ecut :
EJ
Esch are contained in
the induced m–cut. In particular we get
c
EJ
∑
jwjCj
∑
jwjpj
c
Ecut
(17)
whereCjdenotes the completiontime of job jin the sched-
ule corresponding to the partition of J. Since ∑jwjpjand
c
EJ
are constant, minimizing the average weighted com-
pletion time ∑jwjCjof the schedule is equivalent to maxi-
mizing the value c
Ecut
of the induced m–cut. This reduc-
tion of Pm
∑wjCjto MAXmCUT is approximation pre-
serving:
Theorem 5.1. For anyρ
1, aρ–approximationalgorithm
for MAXmCUT translates into an approximation algorithm
for Pm
∑wjCjwith performance guarantee ρ
m
1
ρ
.
Proof. We use the lower bound Z
CQP on the value of an
optimal schedule to get an upper bound on the weight Z
cut
of a maximum m–cut. Lemma 3.2 yields
Z
Z
CQP
1
m
c
EJ
1
2
1
2m
∑
jwjpj(18)
such that
Z
cut
m
1
m
c
EJ
1
2
1
2m
∑
jwjpj(19)
by (17) and (18). Any m–cut in GJwhose weight is at
least ρ
Z
cut therefore yields a schedule whose value can
be bounded as follows:
∑
jwjCj
Z
1
ρ
Z
cut by (17)
Z
1
ρ
m
1
Z
by (19), (18)
ρ
m
1
ρ
Z
Unfortunately, this result does not lead to an improved
performance guarantee for P
∑wjCj. The best currently
known approximation algorithms for MAXmCUT have per-
formance ratio 1
1
m
o
1
m
which leads to performance
guarantee2
1
mfor P
∑jwjCjby Theorem 5.1. It is inter-
esting to mention and easy to see that assigning each vertex
randomly to one of the msubsets is an approximation al-
gorithmwith performanceguarantee 1
1
mfor MAXmCUT.
Moreover, this algorithm coincides with Algorithm RAN-
DOMIZED ROUNDING based on the optimal solution to
CQP
given in Lemma 3.2 and therefore achieves perfor-
mance ratio 3
2
1
2mfor P
∑jwjCjrather than 2
1
m. It
is shown in [21] that MAXmCUT cannot be approximated
within ρ
1
1
34m, unless P=NP.
If we consider the problem for the case m
2 we
get performance guarantee 1
122 if we use the 0
878–
approximation algorithm for MAXCUT by Goemans and
Williamson. This result beats both the 5
4–approximation
in Theorem 3.3 and the 1
2752–approximation in Theo-
rem 4.4. Notice that for the case of two identical parallel
machines
SDP
is a strengthened version of the semidef-
inite programming relaxation for the corresponding MAX-
CUT problem considered in [15]. This leads to the follow-
ing result.
Corollary 5.2. Computing an almost optimal solution to
SDP
and applying Algorithm RANDOM HYPERPLANE
to get a feasible schedule is a 1
122–approximation for
P2
∑wjCj.
This result has been further improved by Goemans [12]
to performance guarantee 1
073 through a more sophisti-
cated rounding technique.
Acknowledgments: I am grateful to Michel Goemans and
Andreas Schulz for helpful comments on an earlier version
of this paper.
References
[1] F. Alizadeh. Interior point methods in semidefinite program-
ming with applications to combinatorial optimization. SIAM
Journal on Optimization, 5:13 – 51, 1995.
[2] D. Bertsimas, C. Teo, and R. Vohra. On dependent ran-
domized rounding algorithms. In W. H. Cunningham, S. T.
McCormick, and M. Queyranne, editors, Integer Program-
ming and Combinatorial Optimization, volume 1084 of Lec-
ture Notes in Computer Science, pages 330 – 344. Springer,
Berlin, 1996.
[3] J. L. Bruno, E. G. Coffman Jr., and R. Sethi. Scheduling
independent tasks to reduce mean finishing time. Communi-
cations of theAssociation for Computing Machinery, 17:382
– 387, 1974.
[4] S. Chakrabarti, C. A. Phillips, A. S. Schulz, D. B. Shmoys,
C. Stein, and J. Wein. Improved scheduling algorithms for
minsum criteria. In F. Meyer auf der Heide and B. Monien,
editors, Automata, Languages and Programming, volume
1099 of Lecture Notes in Computer Science, pages 646 –
657. Springer, Berlin, 1996.
[5] B. Chor and M. Sudan. A geometric approach to between-
ness. In P. Spirakis, editor, Algorithms – ESA ’95, volume
979 of Lecture Notes in Computer Science, pages 227 – 237.
Springer, Berlin, 1995.
[6] F. A. Chudak and D. B. Shmoys. Approximation algorithms
for precedence–constrained scheduling problems on parallel
machines that run at different speeds. In Proceedings of the
8th Annual ACM–SIAM Symposium on Discrete Algorithms,
pages 581 – 590, 1997.
[7] S. J. Chung and K. G. Murty. Polynomially bounded el-
lipsoid algorithms for convex quadratic programming. In
O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, edi-
tors, Nonlinear Programming 4, pages 439 – 485. Academic
Press, 1981.
[8] U. Feige and M. X. Goemans. Approximating the value of
two prover proof systems, with applications to MAX 2SAT
and MAX DICUT. In Proceedings of the Third Israel Sym-
posium on Theory of Computing and Systems, pages 182 –
189, 1995.
[9] A. Frieze and M. Jerrum. Improved approximation algo-
rithms for MAX k-CUT and MAX BISECTION. Algorith-
mica, 18:67 – 81, 1997.
[10] M. X. Goemans. Improved approximation algorithms for
scheduling with release dates. In Proceedings of the 8th An-
nual ACM–SIAM Symposium on Discrete Algorithms, pages
591 – 598, 1997.
[11] M. X. Goemans. Semidefinite programming in combina-
torial optimization. Mathematical Programming, 79:143 –
161, 1997.
[12] M. X. Goemans, June 1998. Personal communication.
[13] M. X. Goemans, M. Queyranne, A. S. Schulz, M. Skutella,
and Y. Wang. Single machine scheduling with release dates,
1998. In preparation.
[14] M. X. Goemans, J. Wein, and D. P. Williamson. A 1.47–
approximation algorithm for a preemptive single-machine
scheduling problem. Manuscript, 1997.
[15] M.X.Goemans and D. P.Williamson. Improved approxima-
tion algorithms for maximum cut and satisfiability problems
using semidefinite programming. Journal of the Association
for Computing Machinery, 42:1115 – 1145, 1995.
[16] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rin-
nooy Kan. Optimization and approximation in deterministic
sequencing and scheduling: A survey. Annals of Discrete
Mathematics, 5:287 – 326, 1979.
[17] M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid
method and its consequences in combinatorial optimization.
Combinatorica, 1:169 – 197, 1981. (Corrigendum: 4(1984),
291 – 295).
[18] M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algo-
rithms and Combinatorial Optimization, volume 2 of Algo-
rithms and Combinatorics. Springer, Berlin, 1988.
[19] L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein.
Scheduling to minimize average completion time: Off–line
and on–line approximation algorithms. Mathematics of Op-
erations Research, 22:513 – 544, 1997.
[20] L. A. Hall, D. B. Shmoys, and J. Wein. Scheduling to min-
imize average completion time: Off–line and on–line algo-
rithms. In Proceedings of the 7th Annual ACM–SIAM Sym-
posium on Discrete Algorithms, pages 142 – 151, 1996.
[21] V. Kann, S. Khanna, and J. Lagergren. On the hardness of
approximating MAX k–Cut and its dual. Chicago Journal
of Theoretical Computer Science, 1997-2, 1997.
[22] D. Karger, R. Motwani, and M. Sudan. Approximate graph
coloring by semidefinite programming. In Proceedings of
the 35th Annual IEEE Symposium on Foundations of Com-
puter Science, pages 2 – 13, 1994.
[23] T. Kawaguchi and S. Kyan. Worst case bound of an LRF
schedule for the mean weighted flow–time problem. SIAM
Journal on Computing, 15:1119 – 1129, 1986.
[24] M. K. Kozlov, S. P. Tarasov, and L. G. Haˇ
cijan. Polynomial
solvability of convex quadratic programming. Soviet Math-
ematics Doklady, 20:1108 – 1111, 1979.
[25] E. L. Lawler and J. M. Moore. A functional equation and its
application to resource allocation and sequencing problems.
Management Science, 16:77 – 84, 1969.
[26] J. K. Lenstra, A. H. G. Rinnooy Kan, and P. Brucker. Com-
plexity of machine scheduling problems. Annals of Discrete
Mathematics, 1:343 – 362, 1977.
[27] J. K. Lenstra, D. B. Shmoys, and E. Tardos. Approxima-
tion algorithms for scheduling unrelated parallel machines.
Mathematical Programming, 46:259 – 271, 1990.
[28] S. Mahajan and H. Ramesh. Derandomizing semidefinite
programming based approximation algorithms. In Proceed-
ings of the 36th Annual IEEE Symposium on Foundations of
Computer Science, pages 162 – 169, 1995.
[29] R. H. Möhring, M. W. Schäffter, and A. S. Schulz. Schedul-
ing jobs with communication delays: Using infeasible so-
lutions for approximation. In J. Diaz and M. Serna, edi-
tors, Algorithms – ESA ’96, volume 1136 of Lecture Notes
in Computer Science, pages 76 – 90. Springer, Berlin, 1996.
[30] R. Motwani, J. Naor, and P. Raghavan. Randomized approx-
imation algorithms in combinatorial optimization. In D. S.
Hochbaum, editor, Approximation algorithms for NP-hard
problems, chapter 11, pages 447 – 481. Thomson, 1996.
[31] A. Munier, M. Queyranne, and A. S. Schulz. Approxima-
tion bounds for a general class of precedence constrained
parallel machine scheduling problems. In R. E. Bixby, E. A.
Boyd, and R. Z. Ríos-Mercado, editors, Integer Program-
ming and Combinatorial Optimization, volume 1412 of Lec-
ture Notes in Computer Science, pages 367 – 382. Springer,
Berlin, 1998.
[32] C. Phillips, C. Stein, and J. Wein. Task scheduling in net-
works. SIAM Journal on Discrete Mathematics, 10:573 –
598, 1997.
[33] C. Phillips, C. Stein, and J. Wein. Minimizing average com-
pletion time in the presence of release dates. Mathematical
Programming, 82:199 – 223, 1998.
[34] C. A. Phillips, A. S. Schulz, D. B. Shmoys, C. Stein, and
J. Wein. Improved bounds on relaxations of a parallel ma-
chine scheduling problem. Journal of Combinatorial Opti-
mization, 1:413 – 426, 1998.
[35] P. Raghavan and C. D. Thompson. Randomized rounding:
A technique for provably good algorithms and algorithmic
proofs. Combinatorica, 7:365 – 374, 1987.
[36] M. H. Rothkopf. Scheduling independent tasks on parallel
processors. Management Science, 12:437 – 447, 1966.
[37] S. Sahni. Algorithms for scheduling independent tasks.
Journal of the Association for Computing Machinery,
23:116 – 127, 1976.
[38] M. W. P. Savelsbergh, R. N. Uma, and J. M. Wein. An
experimental study of LP–based approximation algorithms
for scheduling problems. In Proceedings of the 9th Annual
ACM–SIAM Symposium on Discrete Algorithms, pages 453
– 462, 1998.
[39] A. S. Schulz. Polytopes and Scheduling. PhD thesis, Tech-
nical University of Berlin, Germany, 1996.
[40] A. S. Schulz. Scheduling to minimize total weighted com-
pletion time: Performance guarantees of LP–based heuris-
tics and lower bounds. In W. H. Cunningham, S. T. Mc-
Cormick, and M. Queyranne, editors, Integer Programming
and Combinatorial Optimization, volume 1084 of Lecture
Notes in Computer Science, pages 301 – 315. Springer,
Berlin, 1996.
[41] A. S. Schulz and M. Skutella. Random–based scheduling:
New approximations and LP lower bounds. In J. Rolim, ed-
itor, Randomization and Approximation Techniques in Com-
puter Science, volume 1269 of Lecture Notes in Computer
Science, pages 119 – 133. Springer, Berlin, 1997.
[42] A. S. Schulz and M. Skutella. Scheduling–LPs bear proba-
bilities: Randomized approximations for min–sum criteria.
In R. Burkard and G. J. Woeginger, editors, Algorithms –
ESA ’97, volume 1284 of Lecture Notes in Computer Sci-
ence, pages 416 – 429. Springer, Berlin, 1997.
[43] D. B. Shmoys and E. Tardos. An approximation algorithm
for the generalized assignment problem. Mathematical Pro-
gramming, 62:461 – 474, 1993.
[44] M. Skutella. Approximation and Randomization in Schedul-
ing. PhD thesis, Technical University of Berlin, Germany,
1998.
[45] W. E. Smith. Various optimizers for single–stage produc-
tion. Naval Research and Logistics Quarterly, 3:59 – 66,
1956.
[46] A. Srivastav and K. Wolf. Finding dense subgraphs with
semidefinite programming. In K. Jansen and J. Rolim, ed-
itors, Approximation Algorithms for Combinatorial Opti-
mization, Proceedings of APPROX’98, volume 1444 of Lec-
ture Notes in Computer Science, pages 181 – 191. Springer,
Berlin, 1998.
[47] L. Vandenberghe and S. Boyd. Semidefinite programming.
SIAM Review, 38:49 – 95, 1996.
[48] G. J. Woeginger. When does a dynamic programming for-
mulation guarantee the existence of an FPTAS ? Report
Woe–27, Institut für Mathematik B, Technical University of
Graz, Austria, April 1998.
