arXiv:1509.07808v2 [] 16 Feb 2018

A (1 + ε)-Approximation for Makespan Scheduling with
Precedence Constraints using LP Hierarchies∗
Elaine Levey†

Thomas Rothvoss‡

Abstract
In a classical problem in scheduling, one has n unit size jobs with a precedence
order and the goal is to find a schedule of those jobs on m identical machines as
to minimize the makespan. It is one of the remaining four open problems from the
book of Garey & Johnson whether or not this problem is NP-hard for m = 3.
We prove that for any fixed ε and m, an LP-hierarchy lift of the time-indexed
LP with a slightly super poly-logarithmic number of r = (log(n))Θ(log log n) rounds
provides a (1 + ε)-approximation. For example Sherali-Adams suffices as hierarchy.
This implies an algorithm that yields a (1 + ε)-approximation in time nO(r) . The
7
previously best approximation algorithms guarantee a 2 − 3m+1
-approximation in
4
polynomial time for m ≥ 4 and 3 for m = 3. Our algorithm is based on a recursive
scheduling approach where in each step we reduce the correlation in form of long
chains. Our method adds to the rather short list of examples where hierarchies are
actually useful to obtain better approximation algorithms.

1

Introduction

One of the landmarks in the theory of scheduling is the paper of Graham [Gra66] from
1966, dealing with the following problem: suppose we have a set J of n jobs, each
one with a running time pj along with m identical parallel machines that we can use
to process the jobs. Moreover, the input contains a precedence order on the jobs; we
write j ≺ j ′ if job j has to be completed before job j ′ can be started. The goal is
to schedule the jobs in a non-preemptive fashion so that the makespan is minimized.
Here, the makespan gives the time that the last job is ﬁnished. In the 3-field notation 1 ,
this problem is abbreviated as P | prec | Cmax . Graham showed that the following
∗
The conference version of this work appeared in the 48th ACM Symposium on Theory of Computing
(STOC 2016).
†
University of Washington, Seattle, USA. Email: elevey@cs.washington.edu
‡
University of Washington, Seattle, USA. Email: rothvoss@uw.edu. Supported by NSF grant
1420180 with title “Limitations of convex relaxations in combinatorial optimization” and an Alfred
P. Sloan Research Fellowship.
1
In the 3-field notation, the first field specifies the available processors, the 2nd field the jobs and the
last field the objective function. In our case, P m means that we have m identical machines; pj = 1, prec
indicates that the jobs have unit length and precedence constraints and the last field Cmax specifies
that the objective function is to minimize the maximum completion time.

1

1
)-approximation on the makespan: compute an arbitrary
list schedule gives a (2 − m
topological ordering of the jobs and whenever a machine becomes idle, select the ﬁrst
available job from the list. It had been known since the late 70’s that it is NP-hard to
approximate the problem better than within a factor of 4/3 due to Lenstra and Rinnooy
Kan [LK78] and Schuurman and Woeginger [SW99] prominently placed the quest for any
improvement on their well known list of 10 open problems in scheduling. Finally in 2010,
Svensson [Sve10] showed that assuming a variant of the unique games conjecture [BK09],
there is no (2 − ε)-approximation algorithm for P | prec, pj = 1 | Cmax . However, for
unit size jobs, Lam and Sethi [LS77] analyzed an algorithm of Coﬀman and Graham and
2
for P | prec, pj = 1 | Cmax .
showed that it provides a slighly better guarantee of 2 − m
7
Later, Gangal and Ranade [GR08] gave an algorithm with a 2 − 3m+1
guarantee for
m ≥ 4.
In a typical scheduling application, the number of jobs might be huge compared
to the number of machines, which does justify to ask for the complexity status of
such problems if the number m of machines is a constant. Even under the additional
restriction of unit size jobs, no better approximation result is known. In fact, it is one of
the remaining four open problems from the book of Garey and Johnson [GJ79] whether
P 3 | prec, pj = 1 | Cmax is even NP-hard. Also Schuurman and Woeginger [SW99] list
under “Open Problem 1” the question whether there is a PTAS for this problem (recall
that for m = 2, the result of [LS77] gives an optimum schedule).
To understand where the lack of progress is coming from, one has to go back to
the list scheduling algorithm of Graham. If we schedule the jobs in a greedy manner,
then one can argue that there is always a chain of jobs j1 ≺ j2 ≺ . . . ≺ jk so that at
any point in time either all m machines are P
fully busy or a job from that chain was
1
processed. Since both quantities, the load m j∈J pj and the length of any chain are
lower bounds on any schedule, we can conclude that the schedule has length at most
1
even for general running times, by observing
2 · OP T . One can shave oﬀ a factor of m
that the processing times of the jobs in the longest chain do not need to be again
counted in the load bound. Also the papers [LS77] and [GR08] eﬀectively rely on those
two lower bounds. In fact, [Cha95] showed that a large class of algorithms including the
ones of [Gra66, GR08] cannot beat a bound of 2 − √2m ; moreover Graham’s algorithm

2
)-approximation for unit size jobs, see [GR08].
is indeed not better than a (2 − m
Of course, one always has the option to study the strength of linear programs for an
optimization problem. The most natural one for P m | prec, pj = 1 | Cmax is certainly
the following time-indexed LP: For a parameter T that denotes the length of the time

2

horizon, we deﬁne a set K(T ) as the set of fractional solutions to:
T
X

xj,t = 1

∀j ∈ J

X

xj,t ≤ m

∀t ∈ [T ]

X

≥

t=1

j∈J

t′ <t

xi,t′

X

xj,t′

t′ ≤t

0 ≤ xj,t ≤ 1

(1)

∀i ≺ j ∀t ∈ [T ]
∀j ∈ J ∀t ∈ [T ]

Here xj,t is a decision variable that is supposed to tell whether job j ∈ J is scheduled in
time slot t ∈ [T ], where [T ] := {1, . . . , T }. The constraints guarantee that in an integral
solution each job is assigned to one time slot; no time slot receives more than m jobs
and for a pair of jobs i ≺ j, job i has to be scheduled before j.
Unsurprisingly, this LP has a constant integrality gap as one can see from the
following construction: take k blocks J1 , . . . , Jk of |Ji | = m + 1 jobs each and deﬁne the
precedence order so that all the jobs in Ji have to be ﬁnished before any job in Ji+1 can
be started. Any integral schedule needs two time units per block, hence OP T = 2k.
On the other hand, the LP solution can schedule the m + 1 jobs of each block “in
m
and ﬁnish the schedule after k · m+1
parallel”, each at a rate of m+1
m time units in which
each machine has always been fully busy. This results in an integrality gap of at least
2
.
2 − m+1
It has been long known, that in principle one can take the linear program for any
optimization problem and strengthen it automatically by applying an LP or SDP hierarchy lift. We will provide formal deﬁnitions later, but basically these operators ensure
that for any set of at most r variables, the LP solution indeed lies in the convex hull
of integral combinations. Here, r is the number of levels or rounds and one typically
needs time nO(r) to solve an r-level hierarchy.
Some known approximation results have been reinterpreted in hindsight in this
framework, for example a constant number of Lasserre rounds applied to a basic LP
suﬃces for the Goemans-Williamson algorithm for MaxCut [GW95] and also√a constant number of Lasserre rounds implies the triangle inequalities in the O( log n)approximation algorithm by Arora, Rao and Vazirani [ARV09]. Moreover, the subspace enumeration component in the subexponential time algorithm of Arora, Barak
and Steurer [ABS10] for Unique Games could be replaced with a Lasserre SDP. However,
there are relatively few results where hierarchies have been genuinely useful (at least
fewer than researchers have hoped for). For example Chlamtáč [Chl07] used SDP hierarchies to ﬁnd better colorings in 3-colorable graphs and Raghavendra and Tan [RT12]
apply them to obtain approximation algorithms for CSPs with cardinality constraints.
An application to color hypergraphs can be found in [CS08]. Hierarchies also turned
out to be the right approach for Sparsest Cut in bounded tree width graphs, see the
paper by Chlamtáč, Krauthgamer and Raghavendra [CKR10] and the 2-approximation
by Gupta, Talwar and Witmer [GTW13]. For an application of the Lasserre hierarchy
3

in the context of scheduling, see the recent work of Bansal, Srinivasan and Svensson [BSS16]. Throughout this paper, logarithms will be with respect to base 2, that
means log(T ) := log2 (T ).

1.1

Our Contribution

Our main result is that an LP lift with
2 /ε2 )·log log n)

(log(n))O((m

rounds closes the integrality gap of LP (1) to at most 1 + ε. This implies:
Theorem 1. For the problem P m | prec, pj = 1 | Cmax one can compute a (1 + ε)2 2
approximate solution in time nO(r) where r := (log(n))O((m /ε )·log log n) .
This gives a partial answer to one of the questions under “Open Problem 1” in
[SW99] which asked whether there is a PTAS for this problem. In a Dagstuhl workshop,
Mathieu [Dag10] asked the more speciﬁc question whether the Sherali-Adams hierarchy
gives a (1 + ε)-approximation after c(ε, m) rounds. We also make progress on the
question from the book of Garey and Johnson [GJ79] by improving the 34 -polynomial
time approximation for m = 3 [LS77] to a 1 + ε in slightly more than quasi-polynomial
time. In particular, this implies that P m | prec, pj = 1 | Cmax is not APX-hard,
O(log log n)
).
assuming that NP 6⊆ DTIME(nlog(n)

2

An Explicit LP Hierarchy for Makespan Scheduling

In principle, our result can be obtained by applying the well-known Sherali-Adams
hierarchy to the linear program in (1) — of course the same still holds true for even
more powerful hierarchies such as the Lasserre SDP hierarchy. While this may be the
preferable option for experts, we will work with an explicit strengthening of the above
linear program that hopefully will be more accessible to non-experts in LP hierarchies.
For a set K ⊆ Rm we denote
cone(K) :=

k
nX
i=1

o
λi xi | k ∈ N; xi ∈ K ∀i ∈ [k]; λi ≥ 0 ∀i ∈ [k]

as the convex cone that is spanned by K.
Let us ﬁx a parameter r. Let σ : J → [T ] ∪ {∗} be a partial assignment that
assigns slots only for a subset of jobs. All the jobs with σ(j) = ∗ are unassigned. Let
supp(σ) := {j ∈ J | j is assigned in σ} be the support of that partial assignment. We
denote ∅ as the partial assignment that assigns no job at all. Moreover for a partial
assignment σ and j ∈
/ supp(σ) and t ∈ [T ], let σ ∪ (j, t) be the partial assignment
augmented by σ(j) = t.

4

We say that a solution to SA(K(T ), r) is a set of vectors x := {xσ }|supp(σ)|≤r , where
we deﬁne x := x∅ satisfying the following program:
P
σ∪(j,t)
xσ =
∀σ : |supp(σ)| < r and j ∈
/ supp(σ)
(I)
t∈[T ] x

xσ ∈ cone K(T ) ∩ {x | xj,σ(j) = 1 ∀j ∈ supp(σ)} ∀σ : |supp(σ)| ≤ r (II)
x ∈ K(T )

(III)

In other words, x is a collection of nO(r) many vectors xσ that each has dimension
|J| · T . Note that if xσ is a non-zero vector, then it can be scaled to be a fractional
solution in K(T ) that has all assignments of the partial assignment σ integral. Notice
that we have a variable for each σ with |supp(σ)| ≤ r, so one can ﬁnd a feasible solution
of the program in nO(r) time.
One can think of this system as basically being the Sherali-Adams system, just
that we do include more redundant variables that will make it easy to prove the needed
properties. First, we claim that if there exists a valid schedule σ ∗ , then SA(K(T ), r) 6= ∅.
Here we can build a valid solution by simply choosing xσ as the characteristic vector of
σ ∗ if σ and σ ∗ agree. We set xσ = 0 if there is a job j ∈ supp(σ) so that σ(j) 6= σ ∗ (j).
We give the following useful properties:
P
Lemma 2. Fix some r. Let x ∈ SA(K(T ), r). Let2 λσ := Tt=1 xσj,t . Then the following
holds
xσ
λσ

∈ K(T ) ∩ {x | xj,σ(j) = 1 ∀j ∈ supp(σ)}.

b) If r = n, then x ∈ conv K(T ) ∩ {0, 1}J×[T ] .
a) If λσ > 0, then

∗

∗

c) Let j ∗ ∈ J and t∗ ∈ [T ] so that ρ := xj ∗ ,t∗ > 0. Then taking y σ := 1ρ · xσ∪(j ,t ) for
each σ, one has y = {y σ }|supp(σ)|≤r−1 ∈ SA(K(T ), r − 1) and yj ∗,t∗ = 1. Moreover,
xj,t = 0 ⇒ yj,t = 0 for all j ∈ J and t ∈ [T ].
Proof. We prove the following:
a) Follows from (II) and the deﬁnition of λσ .
b) We can iteratively apply (I) to obtain
x=

X

xσ =

σ:J→[T ]

By a),

xσ
λσ

X

σ:J→[T ]:λσ >0

λσ ·

xσ
.
λσ

are 0/1 vectors.

c) From the deﬁnition we can see that (I), (II) are just inherited. (III) and yj ∗ ,t∗ =
1 follow from the scaling. The implication xj,t = 0 ⇒ yj,t = 0 follows from
(j ∗ ,t∗ )
≤ ρ1 xj,t .
yj,t = 1ρ · xj,t
2

Here j ∈ J is any fixed job. But note that this definition does not depend on the choice of j.

5

If we have solution x ∈ SA(K(T ), r) and variables j ∗ , t∗ with xj ∗ ,t∗ > 0, then
conditioning on xj ∗ ,t∗ = 1 means to replace the solution x with the solution y =
{y σ }|supp(σ)|≤r−1 ∈ SA(K(T ), r − 1) described in Lemma 2.c.

3

An Overview

In this section, we will give an overview over the diﬀerent steps in our algorithm; the
detailed implementation of some of the steps will be given in Section 4, Section 5 and
Section 6. For a given time horizon T , a feasible schedule is an assignment σ : J →
{1, . . . , T } with |σ −1 (t)| ≤ m for all t ∈ [T ] and for all j, j ′ ∈ J one has j ≺ j ′ ⇒ σ(j) <
σ(j ′ ). Formally, our main technical theorem is as follows:
2

Theorem 3. For any solution x ∈ SA(K(T ), r) with r := (log n)O((m /ε
can find a feasible schedule σ : J → N of the jobs in time nO(r) so that

2 )·log log n)

, one

max σ(j) ≤ (1 + ε) · T.
j∈J

To obtain a (1 + ε)-approximation, we can ﬁnd the minimum value of T so that
SA(K(T ), r) 6= ∅ with binary search and then compute a solution x ∈ SA(K(T ), r). In
particular, by virtue of being a relaxation, that value of T will satisfy T ≤ OP T , where
OP T is the makespan of the optimum schedule. For the sake of a simpler notation, we
will assume that T is a power of 2 — if 2z−1 < T ≤ 2z for some integer z, then one
can add m · (2z − T ) many dummy jobs that all depend on each original job so that
the algorithm will schedule the dummy jobs at the very end. Moreover we will assume
that 1ε , m ≤ log(n) as otherwise the bound is meaningless.
The main routine of our algorithm will schedule jobs only within the time horizon T
of the LP-hierarchy solution, but we will allow it to discard jobs. Formally this means,
we will ﬁnd an assignment σ : J \ Jdiscarded → [T ] that will not have assigned slots to
jobs in Jdiscarded . Such an assignment will still be called “feasible” if apart from the load
bound, the condition j ≺ j ′ ⇒ σ(j) < σ(j ′ ) is satisﬁed for all j, j ′ ∈ J \ Jdiscarded . In
particular dependencies with discarded jobs play no role in this deﬁnition.
The reason for this deﬁnition is that one can easily insert the discarded jobs at the
very end of the algorithm:
Lemma 4. Any feasible schedule
σ : J \ Jdiscarded → {1, . . . , T }
can be modified in polynomial time to a feasible schedule
σ ∗ : J → {1, . . . , T + |Jdiscarded |}
which also includes the previously discarded jobs.
6

Proof. Select any job j ∗ ∈ Jdiscarded . Since σ is a valid schedule which respects all
precedence constraints in J \ Jdiscarded , there must be a time t∗ so that all jobs j ≺ j ∗
have σ(j) ≤ t∗ and all jobs j with j ∗ ≺ j have σ(j) > t∗ . Then we insert an extra
time unit after time t∗ ; in this extra time slot, we only process j ∗ . We continue the
procedure with inserting the next job from Jdiscarded \ {j ∗ }.
Now, let us introduce some notation: We can imagine the precedence order “≺”
as a directed transitive graph G = (J, E) with the nodes as jobs and edges (j, j ′ ) ∈
E ⇔ j ≺ j ′ . In that view, let δ+ (j) := {j ′ ∈ J | j ≺ j ′ } be the jobs depending
on j and let δ− (j) := {j ′ ∈ J | j ′ ≺ j} be the jobs on which j depends. Note
that δ+ (j) and δ− (j) are always distinct. We abbreviate δ(j) := δ+ (j) ∪ δ− (j) as
the jobs that have any dependency with j. Finally, for a subset of jobs J ′ ⊆ J, let
∆(J ′ ) := max{|δ(j) ∩ J ′ | + 1 | j ∈ J ′ } be the maximum degree of a node in the
subgraph induced by J ′ , counting also the node itself.
We partition the time horizon [T ] into a balanced binary family I of intervals
of lengths T, T2 , 2T2 , . . . , 2, 1. Let I := I0 ∪˙ . . . ∪˙ Ilog(T ) be the binary laminar family
of intervals that we obtain by repeatedly partitioning intervals into two equally-sized
subintervals. Recall that each level Iℓ contains 2ℓ many interval I ∈ Iℓ ; each one
T
consisting of |I|
P= 2ℓ many time units. For each job j ∈ J and each interval I, we now
deﬁne xj,I := t∈I xj,t , which denotes how much of job j will be scheduled somewhere
within that interval I.
Our algorithm will schedule the jobs in a recursive manner. The main claim is that
for any interval I ∗ , LP-hierarchy solution x∗ and a set of jobs J ∗ with x∗j,I ∗ = 1 we can
schedule almost all jobs from J ∗ within I ∗ while respecting all precedence constraints.
We use parameters k := c1εm log log(T ) where c1 > 0 is a large enough constant
. To get some intuition for the
that we will choose in Section 6, and δ := 2 2kε2
8k m2

log(T )

parameters, considering ε and m as ﬁxed constants, one would have k = Θ(log log n)
and δ = 1/ log(n)Θ(log log n) . Formally, the main technical lemma is the following:
Lemma 5. Fix ε > 0. Let I ∗ ∈ I be an interval from the balanced family of length
T ∗ := |I ∗ |. Let x∗ ∈ SA(K(T ), r ∗ ) be an LP-hierarchy solution with
2

r ∗ ≥ log(T ∗ ) · 2mk2 · 2k /δ.
Let J ∗ ⊆ {j ∈ J : x∗j,I ∗ = 1}. Then one can find a feasible assignment σ : J ∗ \
∗
Jdiscarded
→ I ∗ that discards only
∗
|Jdiscarded
|≤

ε log(T ∗ )
ε
·
· T∗ +
· |J ∗ |
2 log(T )
2m

many jobs.
Before we move on to explain the procedure behind Lemma 5, we want to argue
that it implies our main result, Theorem 3:

7

Proof. We set I ∗ := {1, . . . , T } and x∗ := x, then J ∗ := J is a valid choice as trivially
xj,{1,...,T } = 1 for any job. To satisfy the requirement of Lemma 5 we need
2

log(T ) ·

m 2
2mk2 · 2k
≤ (log(n))O(( ε ) log log(n))
δ

k
many levels of the hierarchy. Here we use that k = Θ( m
ε log log T ), hence 2 =
m
2
2
(log(T ))Θ(m/ε) and 2k = (2k )k = (log(T ))Θ(( ε ) log log T ) (we want to point out that
many of the lower order terms are absorbed into the O-notation of the exponent
and we assume that 1ε , m ≤ log(n)). Then Lemma 5 returns a valid assignment
σ : J \ Jdiscarded → [T ] that discards only

|Jdiscarded | ≤

ε
ε log(T )
·
·T +
· |J| ≤ ε · T
2 log(T )
2m

many jobs. Inserting those discarded jobs via Lemma 4 then results in a feasible schedule
of makespan at most (1 + ε) · T .
The rest of the manuscript will be devoted to proving Lemma 5. We ﬁx a constant
ε > 0 as the target value for our approximation ratio and denote T ∗ := |I ∗ | as the
length of our interval.
Let us ﬁrst argue how to handle the base case, which for us is if log(T ∗ ) ≤ k2 .
2
In that case, we have at most mT ∗ ≤ m2k jobs. Hence, the LP-hierarchy lift has
r ∗ ≥ mT ∗ many levels and one can repeatedly condition on events xj,t = 1 for j ∈ J ∗
and t ∈ I ∗ until one arrives at an LP hierarchy solution x∗∗ with x∗∗
j,t ∈ {0, 1} for all
∗
∗
j ∈ J . This then represents a valid schedule of jobs J in the interval I ∗ without the
need to discard any jobs.
∗
We now come to a high-level description of the algorithm. Let I0∗ , . . . , Ilog(T
∗ ) be
∗

the family of subintervals of I ∗ , where Iℓ∗ contains 2ℓ intervals of lengthPT2ℓ each, see
∗
Figure 1. For a job j ∈ J ∗ , we deﬁne ℓ(j, x∗ ) := max{ℓ : ∃I ∈ Iℓ∗ with
t∈I xj,t = 1}
as the level that owns the job in the current LP-hierarchy solution. We also abbreviate
J(ℓ, x∗ ) := {j ∈ J ∗ | ℓ(j, x∗ ) = ℓ} as all jobs owned by level ℓ. The algorithm is as
follows:
• Step 1: Starting with the LP-hierarchy solution x∗ , we can iteratively condition on events until we arrive at a solution x∗∗ that has the property that
for any interval I ∈ I0∗ ∪ . . . ∪ Ik∗2 −1 , the jobs owned by that interval have
small dependence degree, that
∆(J(I, x∗∗ )) ≤ δ|I|, where J(I, x∗∗ ) :=
P means
∗
∗∗
{j ∈ J | I minimal with
t∈I xj,t = 1}. If we then consider the set of jobs
∗∗
∗
∗∗
J := {j ∈ J | 0 ≤ ℓ(j, x ) < k2 } owned by the ﬁrst k2 levels, the longest
chain in J ∗∗ will contain at most k2 δT ∗ jobs. We will show in Section 4 that the
2
number of required conditionings can be upperbounded by 2mk2 · 2k /δ, which
2
implies that x∗∗ ∈ SA(K(T ), r ∗ − 2mk2 · 2k /δ).

• Step 2: From now on, we work with the modiﬁed LP-hierarchy solution x∗∗ . We
select a level index ℓ∗ ∈ {k, . . . , k2 } and partition the jobs in J ∗ in three diﬀerent
groups:
8

– The jobs on the top levels: Jtop := J(0, x∗∗ ) ∪ . . . ∪ J(ℓ∗ − k − 1, x∗∗ )

– The jobs on the k middle levels: Jmiddle := J(ℓ∗ − k, x∗∗ ) ∪ . . . ∪ J(ℓ∗ − 1, x∗∗ )

– The jobs on the bottom levels: Jbottom := J(ℓ∗ , x∗∗ ) ∪ . . . ∪ J(log(T ∗ ), x∗∗ )

Then we discard all jobs in Jmiddle . In Section 6 we will describe how the index
ℓ∗ is chosen and in particular we will provide an upper bound on the number of
discarded middle jobs.
• Step 3: In this step, we will ﬁnd a schedule for the bottom jobs. For this
purpose, we call Lemma 5 recursively for each interval I ∈ Iℓ∗ with a copy of the
solution x∗∗ and jobs JI := {j ∈ Jbottom | x∗∗
j,I = 1}. Here it is crucial that the
intervals are disjoint but also the sets JI are disjoint for diﬀerent intervals I ∈ Iℓ∗ .
Then Lemma 5 returns a valid schedule of theSform σI : JI \ JI,discarded → I for
each interval I ∈ Iℓ∗ . Let Jbottom-discarded := I∈Iℓ∗ JI,discarded ⊆ Jbottom be the
union of jobs that were discarded in those calls. The partial schedules σI satisfy
/ I. We combine those schedules to
|σI−1 (t)| ≤ m for t ∈ I and |σI−1 (t)| = 0 for t ∈
a schedule
σ : Jbottom /Jbottom-discarded → I ∗ .
From the disjointness of the intervals, it is clear that again |σ −1 (t)| ≤ m for all
t ∈ I ∗ . Moreover, if j ≺ j ′ and j, j ′ ∈ JI for some interval I ∈ Iℓ∗ , then by the
inductive hypothesis σ(j) < σ(j ′ ). On the other hand, if j ∈ JI and j ′ ∈ JI ′ then
∗∗
we know by Lemma 2.c that I had to come before I ′ since x∗∗
j,I = 1 = xj ′ ,I ′ .

• Step 4: We continue working with the previously constructed schedule σ that
schedules the non-discarded bottom jobs. In this step, we will extend the schedule σ and insert the jobs of Jtop in the remaining free slots. We will prove in
Section 5 that this can be done without changing the position of any scheduled
bottom job and without violating any precedence constraints. Again, we allow
that the procedure discards a small number of additional jobs from Jtop that we
will account for later. Eventually, the schedule σ satisﬁes the claim for Lemma 5.
The intuition behind the algorithm is as follows: When we call the procedure recursively for intervals I ∈ Iℓ∗∗ we cannot control where the jobs JI will be scheduled within
that interval I. In particular the decisions made in diﬀerent intervals I, I ′ ∈ Iℓ∗∗ will in
general not be consistent. But the discarding of the middle jobs creates a gap between
the top jobs and the bottom jobs in the sense that the intervals of the top jobs are at
least a factor 2k longer than intervals of the bottom jobs. For a top job j ∈ Jtop we will
be pessimistic and assume that all the bottom jobs that j depends on will be scheduled
just at the very end of their interval. Still, as those intervals are very short, we will
be able to argue that the loss in the ﬂexibility is limited and most of the top jobs can
be processed. As a second crucial ingredient, the conditioning had the implication that
the top jobs do not contain any long chains any more. This will imply that a greedy
schedule of the top jobs will leave little idle time, resulting in only few discarded top
jobs.
9

Jtop

Jmiddle

Jbottom

I0∗
..
.

Iℓ∗∗ −k−1
Iℓ∗∗ −k
..
.
Iℓ∗∗ −1

..

Iℓ∗∗
..
.
Ik∗2 −1
Ik∗2

J ∗∗

..
1

2 ...

T∗

time

Figure 1: Binary dissection of the interval I ∗ used in the algorithm behind Lemma 5.
A high-level pseudo-code description of the whole scheduling algorithm can be found
in Figure 2:

4

Step (1) — Reducing Dependence

In this section we will implement “Step (1)” and show that we can reduce the maximum
dependence degrees of the jobs owned by the ﬁrst k2 levels in order to bound the length
2
of chains. We will do this by conditioning on up to 2mk2 · 2k /δ many variables. We
are considering an interval I ∗ and a subset of jobs J ∗ ⊆ J that the vector x∗ from the
current LP-hierarchy solution x∗ fully schedules within I ∗ . Recall that for one of the
subintervals I ∈ Iℓ∗ below I ∗ , we write J(I, x∗ ) = {j ∈ J(ℓ, x∗ ) | x∗j,I = 1} as the jobs
owned by that particular interval.
Lemma 6. Let x∗ ∈ SA(K(T ), r ∗ ). Then one can find an induced solution x∗∗ ∈
2
SA(K(T ), r ∗∗ ) with r ∗∗ := r ∗ − 2mk 2 · 2k /δ so that ∆(J(I, x∗∗ )) ≤ δ · |I| for all intervals
I ∈ I0∗ ∪ . . . ∪ Ik∗2 −1 .
˙ 2 ∈ I0 ∪ . . . ∪ Ik2 −1
Proof. We set initially x∗∗ := x∗ . If there is any interval I = I1 ∪I
∗∗
with ∆(J(I, x )) > δ · |I|, then we must have a job j ∈ J(I, x∗∗ ) that has either
+
−
+
δ
δ
|δJ(I,x
∗∗ ) (j) ∪ {j}| ≥ 2 · |I| or |δJ(I,x∗∗ ) (j) ∪ {j}| ≥ 2 · |I|. We assume that |δJ(I,x∗∗ ) (j) ∪

{j}| ≥ 2δ · |I| holds and omit the other case, which is symmetric. Then we pick a time
∗∗ by the LP-hierarchy solution conditioned on the
t ∈ I2 with x∗∗
j,t > 0 and replace x
+
∗∗
event “xj,t = 1”. Note that this means that all jobs in δJ(I,x
∗∗ ) (j) ∪ {j} will be removed
∗∗
′
from J(I, x ). In fact, each such job will be moved to J(I , x∗∗ ) where I ′ ⊆ I2 is some
10

QPTAS for Makespan Scheduling
Input: Scheduling instance (J, ≺), parameters m ∈ N and ε > 0
Output: (1 + ε)-approximate schedule σ
(1) Compute a solution x = (xσ )|supp(σ)|≤r
2 2
(log(n))O(m /ε )·log log(n) and T minimal
(2) Call RecursiveScheduling(J, x, [T ]) → σ
(3) Insert discarded jobs into schedule σ

∈

SA(K(T ), r) with r

:=

RecursiveScheduling
P
Input: Jobs J ∗ , LP lift x∗ , interval I ∗ with t∈I ∗ x∗j,t = 1 for j ∈ J ∗
Output: Schedule σ with some jobs discarded
Build binary family of intervals I ∗
Call Breaking Long Chains → x∗∗
Select partition into top, middle, bottom jobs. Pick ℓ∗ .
Discard middle jobs.
For each I ∈ Iℓ∗ set JI := {j ∈ J ∗ | x∗∗
j,I = 1} and
∗∗
call RecursiveSchedule(JI , x , I) → σI
(6) Combine σI ’s to one schedule σ
(7) Call two-phased algorithm based on matching and EDF to insert top jobs into σ
(1)
(2)
(3)
(4)
(5)

Figure 2: High-level description of main algorithm.

11

subinterval. The conditioning can also change the owning interval of other jobs, but for
each job j, the set of times t such that x∗∗
j,t > 0 can only shrink if we condition on any
event, see Lemma 2.c. Hence jobs only move from intervals to subintervals.
∗
Since in each iteration, at least 2δ · |I| ≥ 2δ · Tk2 many jobs “move” and each job moves
2
at most k2 many times out of an interval in I0∗ ∪ . . . ∪ Ik∗2 −1 , we need to condition at
most
k2
2mT ∗ · k2
2 2
= 2mk ·
∗
δ
δ Tk2
2

many times.
The implication of Lemma 6 is that the set of jobs owned by intervals I ∈ I0∗ ∪ . . . ∪
will not contain long chains, simply because we have only few intervals and none
of jobs owned by a single interval contain long chains anymore.

Ik∗2 −1

Lemma 7. After applying Lemma 6, the longest chain within jobs owned by intervals
I ∈ I0∗ ∪ . . . ∪ Ik∗2 −1 has length at most k2 δT ∗ .
Proof. First, let us argue how many jobs a chain can have that are all assigned to
∗
intervals of the same level ℓ. From each interval I, the chain can only include δ|I| = δ· T2ℓ
many jobs. Since |Iℓ | = 2ℓ , the total number of jobs from level ℓ is bounded by δT ∗ .
The claim follows from the pigeonhole principle and the fact that we have k 2 many
levels in I0∗ ∪ . . . ∪ Ik∗2 −1 .
We can summarize the algorithm from Lemma 6 as follows:
Breaking long chains
Input: Scheduling instance with jobs J ∗ , a precedence order, an LP-hierarchy solution x∗ ∈ SA(K(T ), r ∗ ), an interval I ∗
Output: An LP-hierarchy solution x∗∗ with maximum chain length k2 δT ∗ in
Sk2 −1
∗∗
ℓ=0 J(ℓ, x )
(1) Make a copy x∗∗ := x∗
Sk2 −1 ∗
˙ 2 ) ∈ ℓ=0
(2) WHILE ∃I = (I1 ∪I
Iℓ WITH ∆(J(I, x∗∗ )) > δ|I| DO

(3) Choose a job j ∈ J(I, x∗∗ ) with |δJ(I,x∗∗ ) (j) ∪ {j}| ≥ δ|I|.
+
δ
∗∗ on x∗∗ = 1 for some
(4) If |δJ(I,x
∗∗ ) (j) ∪ {j}| ≥ 2 · |I| THEN condition in x
j,t
t ∈ I2
ELSE condition on x∗∗
j,t = 1 for some t ∈ I1 .

Note that after each conditioning in step (6), the solution x∗∗ will change and the set
J(I, x∗∗ ) will be updated.

12

5

Step (4) — Scheduling Top Jobs

Consider the algorithm from Section 3 and the state at the end of Step 3. At this point,
we have a schedule σ that schedules most of the bottom jobs. The main argument that
remains to be shown is how to add in the top jobs which are owned by intervals in
I0∗ ∪ . . . ∪ Iℓ∗∗ −k−1 .
This is done in two steps. First, we use a matching-based argument to show that
most top jobs can be inserted in the existing schedule so that the precedence constraints
with the bottom jobs are respected. In this step, we will be discarding up to 4m·2−k ·T ∗
many jobs. More crucially, the schedule will not have satisﬁed precedence constraints
within Jtop . In a 2nd step, we temporarily remove the top jobs from the schedule and
reinsert them with a variant of the Earliest Deadline First (EDF) scheduling. As we
ε
∗
will see later in Theorem 9, this results in at most 8 log
T · T additionally discarded
jobs.

5.1

A Preliminary Assignment of Top Jobs

Let us recall what we did so far. In Step 3, we applied Lemma 5 recursively on each
interval I ∈ Iℓ∗ to schedule the bottom jobs. We already argued that the resulting
schedules could be combined to a schedule σ : Jbottom /Jbottom-discarded → I ∗ that respects all precedence constraints.
Let the intervals in Iℓ∗∗ be called I1 , . . . , Ip , so that the time horizon T ∗ is partitioned
∗
into p equally sized subintervals with p = 2ℓ . After reindexing the time horizon, let
us assume for the sake of a simpler notation that I ∗ = {1, . . . , T ∗ }. If we abbreviate
∗
ti := i· Tp for i ∈ {0, . . . , p}, then the ith interval contains the time periods Ii := {ti−1 +
1, . . . , ti }. Each time t has an available capacity of cap(t) = m − |σ −1 (t)| ∈ {0, . . . , m}
many machines, which
Pis the number of machines not used by jobs in Jbottom . We
abbreviate cap(Ii ) := t∈Ii cap(t) as the capacity of interval Ii .
The available positions of jobs in Jtop are constrained by the scheduled times of jobs
in Jbottom . As we had no further control over the exact position of the bottom jobs
within their intervals Ii , we want to deﬁne for each job j ∈ Jtop a release time rj and a
deadline dj determined by the most pessimistic outcome of how σ could have scheduled
the bottom jobs. For all j ∈ Jtop , we deﬁne

rj := min ti + 1 | σ(j ′ ) ≤ ti ∀j ′ ∈ Jbottom : j ′ ≺ j
(2)

′
′
′
dj := max ti | σ(j ) ≥ ti + 1 ∀j ∈ Jbottom : j ≺ j
In particular, the release time will be the ﬁrst time unit of an interval Ii and the deadline
will be the last time unit of an interval Ii . Let ir (j) and id (j) be the corresponding
indices, so that the release time is of the form rj = tir (j)−1 + 1 and the deadline is
dj = tid (j) . Then our goal is to show that most top jobs j can be scheduled somewhere
in the time frame Iir (j) ∪ . . . ∪ Iid (j) . This would imply that at least all precedence
constraints between bottom and top jobs are going to be satisﬁed.
Notice here that the existing fractional assignment that x∗∗ provides for j ∈ Jtop
might also be using the slots in the two intervals coming right before and right after the
13

rj

dj
Iir (j)

I1

Iid (j)

tir (j)

Ip

tid (j)

tp
= T∗
˙ p and possible release times and
Figure 3: Visualization of interval I ∗ = I1 ∪˙ . . . ∪I
deadlines for a job j ∈ Jtop . Note that x∗∗ might schedule j over the whole hatched
area, while our choice of rj and dj will force us to process j inside the black-hatched
area (or to discard the job).
t0 1 2

t1

range [rj , dj ] (see Figure 3). This is due to our rounding of release times and deadlines
′
to interval beginnings and ends. Let Jbottom
:= Jbottom \ Jbottom-discarded be the bottom
jobs scheduled by the recursive calls of the algorithm.
′
→ I ∗ of bottom jobs can be extended to a
Lemma 8. A valid schedule σ : Jbottom
′
′
′
⊆ Jtop that includes most of the top jobs.
→ I ∗ with Jtop
∪ Jtop
schedule σ : Jbottom
−1
′
and
The schedule satisfies (i) |σ (t)| ≤ m for t ∈ I ∗ ; (ii) rj ≤ σj ≤ dj for all j ∈ Jtop
′
−k
∗
(iii) one discards at most |Jtop \ Jtop | ≤ 4m · 2 · T many top jobs.

Proof. We want to use a matching-based argument. For this sake, we consider the
bipartite graph with jobs on one side and subintervals on the other. Formally, we deﬁne
a graph G = (V, U, E + ) with V = Jtop , U = {1, . . . , p} where the nodes i ∈ U have
capacity cap(Ii ), and edges
E + = {(j, i) ∈ V × U | max{ir (j) − 1, 1} ≤ i ≤ min{id (j) + 1, p}}.
We say that a matching M is V -perfect if it covers every node in V . Then the neighborhood of each top job includes every interval in which it is fractionally scheduled in x∗∗ .
′
has been assigned by σ to precisely that
Moreover, each of the bottom jobs j ∈ Jbottom
∗∗
∗∗
interval Ii with xj,Ii = 1. Hence x gives a V -perfect fractional matching that respects
the given capacities cap(Ii ). In bipartite graphs, the existence of a fractional V -perfect
matching implies the existence of an integral V -perfect matching, see e.g. [Sch03].
However, in order to assign the top jobs to slots within release times and deadlines
we are only allowed to use the smaller set of edges
E = {(j, i) ∈ V × U | ir(j) ≤ i ≤ idj }.
For any J ∗ ⊆ V , we let N + (J ∗ ) be the neighborhood of J ∗ along edges in E + and let
N (J ∗ ) be its neighborhood along edges in E. Let the magnitude of a neighborhood
|N (J ∗ )| be deﬁned as the sum of capacities of the nodes it contains. By Hall’s Theorem [Sch03], the minimum number of exposed V -nodes in a maximum matching in E
14

is precisely
max{|J| − |N (J)|}.
J⊆V

J∗

Now, ﬁx the set
⊆ V attaining the maximum; then |J ∗ | − |N (J ∗ )| is the number
of jobs that we have to discard. Since E + allows for a V -perfect matching, the reverse direction of Hall’s Theorem gives that |J ∗ | ≤ |N + (J ∗ )|. Thus |J ∗ | − |N (J ∗ )| ≤
|N + (J ∗ )| − |N (J ∗ )|. Note that N (J ∗ ) is in general not a consecutive interval of
∗
{1, . . . , p}. We can upper bound the diﬀerence |N + (J ∗ )| − |N (J ∗ )| by 2m · Tp times the
number of connected components of N (J ∗ ). This is the point where we take advantage
of the “gap” between the levels of the top and bottom jobs: for each job j ∈ V there is
an interval I ∈ I0∗ ∪˙ . . . ∪˙ Iℓ∗∗ −k−1 so that N + (j) contains the midpoint of that interval.
Due to the gap, there are at most p · 2 · 2−k such intervals3 . Hence the number of
discarded jobs can be bounded by
|J ∗ | − |N (J ∗ )| ≤ 2m ·

T∗
· 2p · 2−k = 4m · 2−k · T ∗ .
p

Finally note that a corresponding maximum matching can be computed in polynomial
time.

5.2

Reassigning the Top Jobs via EDF

We have seen so far that we can schedule most of the bottom and top jobs so that all
precedence constraints within the bottom jobs are satisﬁed and the top jobs are correctly
scheduled between the bottom jobs that they depend on. However, the schedule as it
is now ignores the precedence constraints within the top jobs. In this section, we will
remove the top jobs from the schedule and then reinsert them using a variant of the
Earliest Deadline First (EDF) scheduling policy.
For the remainder of Section 5.2, we will show a stand-alone theorem that we will
use as a black box. Imagine a general setting where we have m identical machines and
n jobs J, each one with integer release times rj and deadlines dj and a unit processing
time. The EDF scheduling rule picks at any time the available job with minimal dj for
processing. It is a classical result in scheduling theory by Dertouzos [Der74] that for
m = 1 and unit size jobs, EDF is an optimal policy. Here “optimal” means that if there
is any schedule that ﬁnishes all jobs before their deadline, then EDF does so, too. The
result extends to the case of arbitrary running times pj if one allows preemption.
Now, our setting is a little bit diﬀerent. For each time t, we have a certain number
cap(t) ∈ {0, . . . , m} of slots. Additionally, we have a precedence order that we need
to respect. But we can use to our advantage that the precedence order has only short
chains; moreover, the number of diﬀerent release times and deadlines is limited.
Formally we will prove the following:
It is possible that N (j) = ∅. Still N + (j) will contain a midpoint of a level 0, . . . , ℓ∗ − k − 1 interval,
hence we have accounted for those jobs as well. Note that such jobs would automatically get discarded.
3

15

Theorem 9. Let J be a set of jobs with release times rj , deadlines dj and consistent precedence constraints4 with maximum chain length C. Suppose that {1, . . . , T }
is the time horizon, partitioned into equally sized intervals I1 , . . . , Ip and all release
times/deadlines correspond to beginnings and ends of those intervals. Let cap : [T ] →
{0, . . . , m} be a capacity function and assume that there exists a schedule σ̃ : J → [T ]
assigning each job to slots between its release time and deadline that respects capacities
but does not necessarily respect precedence constraints within J.
Then in polynomial time, one can find a schedule σ : J \ Jdiscarded → [T ] that
respects capacities, release times, deadlines and precedence constraints and discards
|Jdiscarded | ≤ p2 mC many jobs.
We use the following algorithm, which is a variant of Earliest Deadline First, where
we discard those jobs that we cannot process in time:
Earliest Deadline First
Input: Jobs J with deadlines, release times, precedence constraints; capacity function cap : [T ] → {0, . . . , m}
Output: Schedule σ : J → [T ] ∪ {DISCARDED}
(1) Set σ(j) := UNASSIGNED for all j ∈ J and Jdiscarded := ∅
(2) Sort the jobs J = {1, . . . , n} so that d1 ≤ d2 ≤ . . . ≤ dn
(3) FOR t = 1 TO T DO
(4) FOR cap(t) MANY TIMES DO
(5) Select the lowest index j of a job with rj ≤ t ≤ dj that has not
been scheduled or discarded and that has all jobs in δ− (j) already
processed (or discarded).
(6) Set σ(j) := t (if there was any such job)
(7) FOR each j ∈ J with dj = t and σ(j) = UNASSIGNED, add j to Jdiscarded
and set σ(j) := DISCARDED
At the end all jobs j will be either scheduled between rj and dj (that means rj ≤ σ(j) ≤
dj ) or they are in Jdiscarded .
We will say that a job j was discarded in the interval [t, t′ ] if j ∈ Jdiscarded and
t ≤ dj ≤ t′ . We call a time t busy if |σ −1 (t)| = cap(t) and non-busy otherwise. Let us
make a useful observation:
Lemma 10. Let I = {t′ , . . . , t′′ } ⊆ Ii be part of one of the subintervals. Suppose
that there is a non-busy time t∗ ∈ I and a job j with I ⊆ {rj , . . . , dj } and σ(j) ∈
{DISCARDED} ∪ {t′′ + 1, . . . , T }. Then there is a job j ∗ ∈ σ −1 (t∗ ) with j ∗ ≺ j.
Proof. Consider any inclusion-wise maximal chain of jobs j1 ≺ j2 ≺ . . . ≺ jq that ends in
j = jq and otherwise has only jobs j1 , . . . , jq−1 ∈ σ −1 ({t∗ , . . . , t′′ }). First suppose that
q > 1 and hence j1 6= j. It is impossible that σ(j1 ) > t∗ because by assumption rj1 ≤ t∗
4

Here “consistent” means that for a pair of dependent jobs j ≺ j ′ one has rj ≤ rj ′ and dj ≤ dj ′ .

16

and hence EDF would have processed j1 already earlier at time t∗ (by maximality of the
chain, there is no job scheduled at times t∗ , . . . , σ(j1 ) − 1 on which j1 might depend).
Hence σ(j1 ) = t∗ and by transitivity j1 ≺ j, which gives the claim.
In the 2nd case, we have j1 = j, hence there is no job that j depends on scheduled
between t∗ and t′′ . But we know that rj ≤ t∗ . Thus EDF would have processed j at
time t∗ or earlier.
With this observation we can easily limit the number of non-busy times per interval:
Lemma 11. Let I = {t′ , . . . , t′′ } ⊆ Ii be part of one of the subintervals. Suppose that
there is at least one job j with I ⊆ {rj , . . . , dj } and σ(j) ∈ {DISCARDED}∪{t′′ +1, . . . , T }.
Then the number of non-busy times in I is bounded by C.
Proof. By Lemma 10, for the latest time t∗ ∈ I with |σ −1 (t∗ )| < cap(t∗ ), there is at
least one job j ∗ ∈ σ −1 (t∗ ) with j ∗ ≺ j. Then we can continue by induction, replacing
t′′ with t∗ − 1 and replacing j by j ∗ to build a chain of jobs ending with j that includes
a job scheduled at each non-busy time. Since no chains can be longer than C, this gives
the claim.
Now we come to the main argument where we give an upper bound of the number
of discarded jobs:
Lemma 12. One has |Jdiscarded | ≤ p2 mC.
Proof. Suppose that |Jdiscarded | ≥ p · K; we will then derive a bound on K. By the pigeonhole principle, we can ﬁnd an interval Ib so that at least K many jobs get discarded
in Ib . Let us denote the lowest priority (i.e. the latest deadline) job that gets discarded
in Ib by js . Now delete all those lower priority jobs js+1 , . . . , jn . Note that this does not
aﬀect how EDF schedules j1 , . . . , js and still we would have at least K jobs discarded
in Ib , including js . By Lemma 11, the number of non-busy periods in Ib is bounded
by C. Now, choose a minimal index a ∈ {1, . . . , b − 1} so that in each of the intervals
Ia , . . . , Ib one has at most C many non-busy periods. We abbreviate I ′ := Ia ∪ . . . ∪ Ib .
Note that by deﬁnition Ia−1 has more than C many non-busy periods5 . Deﬁne
n
o
J ′ := j ∈ {j1 , . . . , js } : (σ(j) ∈ I ′ ) or (j discarded and dj ∈ I ′ ) .
By Lemma 10, any job in J ′ has its release time in Ia or later, since otherwise we could
not have C + 1 non-busy times in Ia−1 . Now, let us double count the number of jobs
in J ′ . On the one hand, we have
′

|J | ≥

b
X
i=a

|σ

−1

b
X
(cap(Ii ) − mC) + |J ′ ∩ Jdiscarded |
(Ii )| + |J ∩ Jdiscarded | ≥
{z
}
|
′

i=a

′

≥ cap(I ) − pmC + K.

≥K

5
Admittedly it is possible that a = 1 in which case one might imagine I0 as an interval in which all
times are non-busy and which does not contain any release times.

17

On the other hand, we know that there is an assignment σ̃ of jobs in J ′ to slots in
Ia , . . . , Ib . That tells us that |J ′ | ≤ cap(I ′ ). Comparing both bounds gives that K ≤
pmC.

6

Step (2) — Accounting for Discarded Jobs

In this section, we need to argue that the level ℓ∗ can be chosen so that the total number
of jobs that are discarded in Steps (1)-(4) are bounded by
∗
|Jdiscarded
|≤

ε log(|I ∗ |)
ε
·
· |I ∗ | +
· |J ∗ |
2 log(T )
2m

as claimed. Let us summarize the three occasions in the algorithm where a job might
get discarded:
∗

(A) In Step (3), in order to schedule the bottom jobs, we have 2ℓ many recursive calls
of Lemma 5 for intervals I ∈ Iℓ∗∗ . The cumulative number of discarded jobs from
all those calls is bounded by
∗

T
ε log( 2ℓ∗ ) T ∗
ε
ε log(T ∗ ) − ℓ∗
ε
2 · ·
· ℓ∗ +
· |Jbottom | = ·
· T∗ +
· |Jbottom |
2 log(T ) 2
2m
2
log(T )
2m
ℓ∗

(B) As we have seen in Section 5, the number of top jobs that need to be discarded
in Step (4) can be bounded by
2

4m · 2−k · T ∗ + p2 mC ≤ 4m · 2−k · T ∗ + k2 m22k T ∗ δ ≤

ε
1
·
· T ∗.
4 log(T )

Here we use that the length of the maximum chain within the top jobs is C ≤
2
∗
k2 δT ∗ . Moreover, we have substituted the parameters p = 2ℓ ≤ 2k as well as
and k = c1 m
δ = 2 2kε2
ε log log(T ) with a large enough constant c1 > 0.
8k m2

log(T )

(C) In Step (2), we discard all the middle jobs. In the remainder of this section we
prove that there is an index ℓ∗ so that
|Jmiddle | ≤

ε
1
ε
·
· T∗ +
· (|Jmiddle | + |Jtop |)
4 log(T )
2m

Let us ﬁrst assume that we can indeed ﬁnd a proper index ℓ∗ so that the bound in

18

(C) is justiﬁed. Then the total number of jobs that the algorithm discards is
(A)

(B)

}|
{ z
z
}|
{
ε
ε log(T ∗ ) − ℓ∗
ε
1
∗
·
·T +
· |Jbottom | + ·
· T∗
2
log(T )
2m
4 log(T )
(C)

}|
{
z
ε
1
ε
∗
+ ·
·T +
· (|Jmiddle | + |Jtop |)
4 log(T )
2m
ε
ε log(T ∗ )
·
· T∗ +
· (|Jtop | + |Jmiddle | + |Jbottom |)
≤
2 log(T )
2m |
{z
}
=|J ∗ |

which is the bound that we claimed in Lemma 5.
It remains to justify the claim in (C). We abbreviate αi := |J(i · k, x∗∗ ) ∪ . . . ∪
J((i + 1) · k − 1, x∗∗ )| for i ∈ {0, . . . , k − 1}. In words, each number αi represents the
number of jobs owned by k consecutive levels. We observe that if there is an index
i ∈ {0, . . . , k − 1} so that
ε
· T∗
(I) αi ≤
4 log(T )

or

i
ε X
αj
(II) αi ≤
·
2m
j=1

then we can choose ℓ∗ := (i + 1) · k and (C) will be satisﬁed. Here we use that for this
particular choice of ℓ∗ , we will have |Jmiddle | = αi and |Jtop | = α0 + . . . + αi−1 .
So, we assume for the sake of contradiction that no index i satisﬁes either (I) or
(II) (or both). Then one can easily show that the αi ’s have to grow exponentially. We
show this in a small lemma:
Lemma 13. Let q ∈ N and suppose we P
have a sequence of numbers α0 , α1 , . . . , αN
1
satisfying αi ≥ αmin > 0 and αi ≥ q · ij=1 αj for all i = 0, . . . , N . Then αi ≥
2⌊i/(2q)⌋ · αmin .
Proof. Group the indices into consecutive blocks of 2q numbers, where α0 , . . . , α2q−1 is
block 0, α2q , . . . , α4q−1 is block 1 and so on. We want to prove by induction that each αi
in the jth block is at least 2j · αmin . For j = 0, the claim follows from the assumption.
For j > 0, we use that αi is at least the sum of 2q numbers that by inductive hypothesis
j−1
are all at least 2 q · αmin . The claim follows.
2m
ε
∗
Applying Lemma 13 with αmin := 4 log(T
) · T and q := ε we obtain in particular
that
ε
ε
· T∗
αk−1 ≥ 2⌊(k−1) 4m ⌋ ·
4 log(T )

If we set k = c1εm log(log(T )) for some adequately large c1 , then αk−1 > mT ∗ , which is
a contradiction since we only have |J ∗ | ≤ m · |I ∗ | = mT ∗ many jobs with xj,I ∗ = 1.
19

7

Conclusion

For the proof of Lemma 5 we already argued that the number of discarded jobs satisﬁes
the claimed bound and that all precedence constraints will be satisﬁed. Regarding
the number of rounds in the hierarchy, recall that we started with a solution x∗ ∈
2
SA(K(T ), r ∗ ) with r ∗ ≥ log(T ∗ ) · 2mk2 · 2k /δ. Then we apply a round of conditionings
2
in Lemma 6 to obtain x∗∗ ∈ SA(K(T ), r ∗∗ ) with r ∗∗ := r ∗ − 2mk2 · 2k /δ. We use
copies of the solution x∗∗ in our recursive application of Lemma 5 to intervals of size
∗
T ∗ /2ℓ . Since ℓ∗ ≥ k ≥ 1, the remaining number of LP-hierarchy rounds satisﬁes
2
∗
r ∗∗ ≥ log(T ∗ /2ℓ ) · 2mk2 · 2k /δ. Thus we still have enough LP-hierarchy rounds for the
recursion.
Another remark concerns why we may assume that the precedence constraints are
consistent in Theorem 9. Suppose we have jobs j, j ′ ∈ Jtop with j ≺ j ′ and consider the
deﬁnition of release times and deadlines in Eq. 2. By transitivity, any job j ′′ ∈ Jbottom
with j ′ ≺ j ′′ which limits the deadline of j ′ will also limit the deadline of j, hence
dj ≤ dj ′ . Similarly one can argue that rj ≤ rj ′ . This concludes the proof of Lemma 5
and our main result follows.

8

Follow-up work and open problems

A natural question that arises is whether the number of O(log n)O(log log n) rounds for
constant ε, m can be improved. In fact, after the conference version of this paper appeared, Garg [Gar17] was able to reduce the number of rounds down to O(log n)O(1) ,
hence providing an actual QPTAS. It remains open whether c(m, ε) many rounds sufﬁce as well. Another tantalizing question is whether a similar approach could give a
(1 + ε)-approximation for P m | prec | Cmax , where the processing times pj ∈ N are
arbitrary. Note that the diﬃculty in this setting comes from the issue that jobs have
to be scheduled non-preemptively.

References
[ABS10]

S. Arora, B. Barak, and D. Steurer. Subexponential algorithms for unique
games and related problems. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas,
Nevada, USA, pages 563–572, 2010.

[ARV09] S. Arora, S. Rao, and U. V. Vazirani. Expander ﬂows, geometric embeddings
and graph partitioning. J. ACM, 56(2), 2009.
[BK09]

N. Bansal and S. Khot. Optimal long code test with one free bit. In Foundations of Computer Science, 2009. FOCS ’09. 50th Annual IEEE Symposium
on, pages 453–462, Oct 2009.

20

[BSS16]

N. Bansal, S. Srinivasan, and O. Svensson. Lift-and-round to improve
weighted completion time on unrelated machines. In Proceedings of the 48th
Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016,
Cambridge, MA, USA, June 18-21, 2016, pages 156–167, 2016.

[Cha95]

M. Charikar. Approximation algorithms for problems in combinatorial optimization. Technical report, B. Tech. Project Report, Department of Computer Sc. and Engg., IIT Bombay, 1995.

[Chl07]

E. Chlamtac. Approximation algorithms using hierarchies of semideﬁnite
programming relaxations. In 48th Annual IEEE Symposium on Foundations
of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI,
USA, Proceedings, pages 691–701, 2007.

[CKR10] E. Chlamtac, R. Krauthgamer, and P. Raghavendra. Approximating sparsest
cut in graphs of bounded treewidth. In Approximation, Randomization, and
Combinatorial Optimization. Algorithms and Techniques, 13th International
Workshop, APPROX 2010, and 14th International Workshop, RANDOM
2010, Barcelona, Spain, September 1-3, 2010. Proceedings, pages 124–137,
2010.
[CS08]

E. Chlamtac and G. Singh. Improved approximation guarantees through
higher levels of SDP hierarchies. In Approximation, Randomization and
Combinatorial Optimization. Algorithms and Techniques, 11th International
Workshop, APPROX 2008, and 12th International Workshop, RANDOM
2008, Boston, MA, USA, August 25-27, 2008. Proceedings, pages 49–62,
2008.

[Dag10]

Open problems – scheduling. In Susanne Albers, Sanjoy K. Baruah, Rolf H.
Möhring, and Kirk Pruhs, editors, Scheduling, number 10071 in Dagstuhl
Seminar Proceedings, Dagstuhl, Germany, 2010. Schloss Dagstuhl - LeibnizZentrum fuer Informatik, Germany.

[Der74]

M. L. Dertouzos. Control robotics: The procedural control of physical processes. In IFIP Congress, pages 807–813, 1974.

[Gar17]

S. Garg. Quasi-ptas for scheduling with precedences using LP hierarchies.
CoRR, abs/1708.04369, 2017.

[GJ79]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to
the Theory of NP-Completeness. W. H. Freeman and Company, New York,
New York, 1979.

[GR08]

D. Gangal and A. Ranade. Precedence constrained scheduling in optimal.
Journal of Computer and System Sciences, 74(7):1139 – 1146, 2008.

[Gra66]

R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System
Technical Journal, 45(9):1563–1581, 1966.
21

[GTW13] A. Gupta, K. Talwar, and D. Witmer. Sparsest cut on bounded treewidth
graphs: algorithms and hardness results. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages
281–290, 2013.
[GW95]

M. X. Goemans and D. P. Williamson. Improved approximation algorithms
for maximum cut and satisﬁability problems using semideﬁnite programming.
J. ACM, 42(6):1115–1145, 1995.

[LK78]

J. K. Lenstra and A. H. G. Rinnooy Kan. Complexity of scheduling under
precedence constraints. Operations Research, 26(1):22–35, 1978.

[LS77]

S. Lam and R. Sethi. Worst case analysis of two scheduling algorithms. SIAM
J. Comput., 6(3):518–536, 1977.

[RT12]

P. Raghavendra and N. Tan. Approximating csps with global cardinality constraints using SDP hierarchies. In Proceedings of the Twenty-Third Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan,
January 17-19, 2012, pages 373–387, 2012.

[Sch03]

A. Schrijver. Combinatorial Optimization - Polyhedra and Efficiency.
Springer, 2003.

[Sve10]

O. Svensson. Conditional hardness of precedence constrained scheduling on
identical machines. In Proceedings of the Forty-second ACM Symposium on
Theory of Computing, STOC ’10, pages 745–754, New York, NY, USA, 2010.
ACM.

[SW99]

P. Schuurman and G. J. Woeginger. Polynomial time approximation algorithms for machine scheduling: ten open problems. Journal of Scheduling,
2(5):203–213, 1999.

22

