Lazy Local Search Meets Machine Scheduling
Chidambaram Annamalai∗

arXiv:1611.07371v2 [cs.DS] 13 Dec 2016

December 14, 2016

Abstract
We study the restricted case of Scheduling on Unrelated Parallel Machines. In this
problem, we are given a set of jobs J with processing times pj and each job may be scheduled
only on some subset of machines Sj ⊆ M . The goal is to find an assignment of jobs to machines
to minimize the time by which all jobs can be processed. In a seminal paper, Lenstra, Shmoys,
and Tardos [LST87] designed an elegant 2-approximation for the problem in 1987. The question
of whether approximation algorithms with better guarantees exist for this classic scheduling
problem has since remained a source of mystery.
In recent years, with the improvement of our understanding of Configuration LPs, it now
appears an attainable goal to design such an algorithm. Our main contribution is to make
progress towards this goal. When the processing times of jobs are√either 1 or ǫ ∈ (0, 1), we
design an approximation algorithm whose guarantee tends to 1 + 3/2 ≈ 1.8660254, for the
interesting cases when ǫ → 0. This improves on the 2 − ǫ0 guarantee recently obtained by
Chakrabarty, Khanna, and Li [CKL15] for some constant ǫ0 > 0.
Keywords: scheduling, unrelated parallel machines, restricted assignment, configuration linear programs.

∗

Department of Computer Science, ETH Zurich. Email: cannamalai@inf.ethz.ch.

1

Introduction

We study a special case of the problem of Scheduling on Unrelated Parallel Machines.
An instance I of this problem consists of machines M , jobs J, and a collection of positive processing
times {pij }i∈M,j∈J for every machine–job pair. The goal is to assign all the jobs to the available
machines such that the makespan of the resulting schedule is as small as possible. The makespan
of a schedule σ : J 7→ M is deﬁned as
X
max
pij .
i∈M

j∈σ−1 (i)

It is one of the major open questions [WS11] in the ﬁeld of approximation algorithms to better
understand the approximability of this problem. Curiously, the best known hardness result and
approximation algorithm for the problem today were simultaneously established in the 1987 paper
of Lenstra, Shmoys and Tardos [LST87].
Given the challenging nature of the problem, the road to a better understanding of its approximability has focused on two special cases that each isolate two diﬃcult aspects associated with
it—on the one hand a given job j ∈ J may be assigned with a ﬁnite processing time to an unbounded
number of machines, and on the other hand, its processing time may vary considerably across those
machines. In the graph balancing case, only instances where every job may be assigned to at most
two machines with ﬁnite processing time are considered. In the restricted case, often referred to as
the restricted assignment makespan minimization problem, the input processing times obey
the condition pij ∈ {∞, pj } for each i ∈ M and j ∈ J, where pj is a machine independent processing
time for job j. This has the natural interpretation that each job has a ﬁxed processing time but
may only be scheduled on some subset of the machines. The latter special case is the focus of this
work.
The elegant 2-approximation of Lenstra et al. [LST90] works by rounding extreme point solutions
to a linear program called the Assignment LP. As this linear program has a matching integrality
gap, one of the natural directions was to develop a stronger convex relaxation for the restricted
case. An important step forward was made by Bansal and Sviridenko [BS06] who, among other
things, introduced the Conﬁguration LP for the problem, which has exponentially many decision
variables. At the time, however, it was not clear if this new linear program was indeed stronger than
the Assignment LP in the sense of a worst case integrality gap. A breakthrough in this direction
was achieved by Svensson [Sve12] who proved that the integrality of the Conﬁguration LP is no
worse than 33/17 ≈ 1.94, and, therefore, strictly better than the Assignment LP. Tantalizingly,
however, the proof of his result did not lead to an approximation algorithm with the same (or even
similar) guarantee. This is a fairly strange situation for a problem, as we usually expect integrality
gap upper bounds to accompany an approximation algorithm; indeed, it is often established as a
consequence of the latter.
The diﬃculties in turning the non-constructive aspects of Svensson’s result into an eﬃcient algorithm mirror the situation faced in the restricted max-min fair allocation problem. In
the latter problem, following a long line of work [BS06, Fei08, HSS11, AFS12, PS12, AKS15], a
non-constructive integrality gap upper bound on the Conﬁguration LP by Asadpour, Feige and
Saberi [AFS12] was turned into an approximation algorithm [AKS15]. Although one might reasonably hope for a similar resolution in the restricted case, it has proved to be elusive thus far. Indeed,
there have been works aimed at obtaining better-than-2 approximation algorithms for special cases,
2

and the gap between the 33/17 ≈ 1.94 (recently improved to 11/6 ≈ 1.83 [JR16]) integrality gap
upper bound and the 2 approximation algorithm of Lenstra et al. [LST90] persists. Ebenlendr, Křćal
and Sgall [EKS08] studied the case when jobs may be assigned to at most two machines and gave a
1.75 approximation in this case. Recently, Chakrabarty, Khanna, and Li [CKL15] designed a 2 − ǫ0
approximation algorithm, for some constant ǫ0 > 0, for the so-called (1, ǫ)-case where processing
times of jobs are drawn from a set of size two.
The special signiﬁcance of (1, ǫ)-case is that it already proves to be hard from the perspective
of the Conﬁguration LP—the best known 1.5 factor integrality gap instances are of this type—and
seems to adequately capture the diﬃculty of the restricted case in general. It is also interesting in
its own right, and in a sense it is the simplest case of the problem that is not yet fully understood.
Indeed, the case when processing times of all the jobs are equal can be solved optimally in polynomial
time: this amounts to ﬁnding a maximum ﬂow in an appropriate ﬂow network with jobs as sources,
machines as sinks, and setting the sink capacities to be uniformly equal to some guess on the
optimum makespan.
Our Results. After normalizing the job sizes, we assume without loss of generality that the jobs
are of size 1 or ǫ for some 0 < ǫ < 1. Our main result is a new purely ﬂow based local search
algorithm for the (1, ǫ)-case.
Theorem 1.1. Let 0 < ǫ < 1. For an arbitrary but fixed ζ > 0, the (1, ǫ)-case of restricted assignment makespan minimization admits a polynomial time 1 + R(ǫ, ζ) approximation algorithm
where

∆ 1 √
3 − 2ǫ + ǫ + ζ.
R(ǫ, ζ) =
2

From the point of view of better-than-2 approximation algorithms, the hard case is when√ǫ → 0.
For this range of values, the approximation ratio guaranteed by Theorem 1.1 tends to 1 + 3/2 ≈
1.87. By balancing against a simple algorithm based on bipartite matching we also derive an
approximation guarantee independent of the size of small jobs.

Theorem 1.2. Let 0 < ǫ < 1. For an arbitrary but fixed ζ > 0, the (1, ǫ)-case of restricted
assignment makespan minimization admits a polynomial time 17/9+ζ approximation algorithm.
Note that 17/9 ≈ 1.89.
Our Techniques. We now give a very high level overview of the ideas behind the proof of Theorem 1.1 assuming that the optimum makespan is 1 for simplicity.
Our local search algorithm continually increases the number of jobs
P scheduled by an assignment
σ : M 7→ J ∪ {TBD}1 that satisﬁes the 1 + R makespan bound i.e., j∈σ−1 (i) pij ≤ 1 + R for each
i ∈ M . The algorithm takes a job j0 such that σ(j0 ) = TBD and attempts to assign it to one of
the machines M while respecting the makespan bound of 1 + R. In general, it may be required to
modify the assignment σ, which we call a partial schedule, before j0 can be successfully assigned
along with the rest of the jobs in σ −1 (M ). The algorithm identiﬁes a set of machines M0 such
that suﬃciently reducing the load on any of the machines i ∈ M0 suﬃces to assign j0 successfully.
Once again, to reduce the load on one of the machines in M0 a new set of machines M1 that is
disjoint from M0 is identiﬁed. In this way, in general there will be a sequence of disjoint machine
sets M0 , M1 , . . . , Mℓ such that reducing the load on some Mi allows the load to be reduced on some
1

TBD for “to be decided”

3

machine in M0 ∪ . . . ∪ Mi−1 . At some point, it may turn out that a lot of machines in Mℓ have
very little load, call them free machines, and therefore, it is possible for many of the jobs currently
scheduled on some machine in M0 ∪ . . . ∪ Mℓ−1 to be relocated to free machines in Mℓ , which
represents progress towards our goal of eventually scheduling j0 .
The ﬁrst property we require is large progress which ensures that many free machines in Mℓ
implies that proportionally many jobs from σ −1 (M0 ∪ . . . ∪ Mℓ−1 ) can be relocated. Further, such
relocations should be performed in a way as to maintain the same property for the machine sets of
smaller indices.
Large progress by itself would not guarantee that the algorithm terminates quickly if it does
not happen often enough. To ensure that we ﬁnd many free machines frequently, a second property
ensures |Mi | ≥ µ|M0 ∪ . . . ∪ Mi−1 | so that large progress happens at least once every Oµ (log |M |)
sets that are encountered.
These two properties–and maintaining them as the partial schedule is continually modiﬁed by
the algorithm–roughly correspond to the core technical diﬃculties of our approach. The proof of the
ﬁrst property (see Section 3.3.4) makes fairly extensive use of properties of maximum ﬂows, while
the second property (see Section 3.3.5) is based on new ideas for constructing dual unboundedness
certiﬁcates for the Conﬁguration LP. It is interesting to note that the construction of such certiﬁcates
in the analysis, to prove the required property about the local search algorithm, eﬀectively amounts
to a second algorithm that is merely used to determine an assignment of values to the dual variables
in the proof.
Our ﬁnal algorithm is a highly structured local search that performs job relocations only through
ﬂow computations in two kinds of ﬂow networks. In essence, our approach can be seen as eﬀectively
reducing the scheduling problem we started with to polynomially many maximum ﬂow computations
in a structured fashion. The sets alluded to earlier correspond to certain “reachability graphs”
associated with ǫ jobs whereas the number of such sets at any time is bounded by a function of the
number of 1 jobs in the instance. We also stress that identifying such sets, which allow our analyses
to prove these properties, requires a careful design of the algorithm in the ﬁrst place, and is not
clear at the outset that this can be achieved.
Organization. The rest of the paper is organized as follows. In Section 2, we brieﬂy go over
some notation and state the Conﬁguration LP for our problem. In Section 3.1 we explain some of
the basic concepts such as ﬂow networks and subroutines for job relocations used in the ﬁnal local
search algorithm. The algorithm and its running time analysis are presented in Sections 3.2 and 3.3
respectively, followed by the proof of the main theorem in the paper in Section 3.4. Proofs of some
statements missing in the body of the paper appear in Appendix A.

2
2.1

Preliminaries
Notation and Conventions

Let I be the given instance of restricted assignment makespan minimization. By scaling all
∆
the processing times in the instance, we assume without loss of generality that pmax = max{pj | j ∈
J} = 1. We use OPT to denote the optimal makespan for I.
P
P
For a subset of jobs S ⊆ J, we use the notation p(S) and pi (S) to refer to j∈S pj and j∈S pij
respectively. We deﬁne Γ : J 7→ 2M to be a function that maps each job j ∈ J to the set of
4

all machines that it can be assigned to with a ﬁnite processing time. The input processing times
{pij }i∈M,j∈J and {pj }j∈J satisfy
(
pj , if i ∈ Γ(j),
∀i ∈ M ∀j ∈ J.
pij =
∞, else.
For S
a collection of indexed sets {S0 , . . . , Sℓ } and 0 ≤ i ≤ ℓ we use the notation S≤i to refer to the
set ij=0 Sj .

2.2

The Configuration Linear Program

The Conﬁguration LP is a feasibility linear program parametrized by a guess τ on the value of the
optimal makespan for I, and is simply denoted by CLP (τ ). A configuration for machine i is a set
of jobs with a total processing time at most τ on machine i. The collection of all such conﬁgurations
for i is denoted as C(i, τ ). CLP (τ ) ensures that each machine receives at most one conﬁguration
fractionally, while ensuring that every job is assigned, also in the fractional sense. The constraints
of CLP (τ ) are described in (2.1).
X
xiC ≤ 1, ∀i ∈ M,
C∈C(i,τ )

X

X

i∈M C∈C(i,τ ) : j∈C

xiC ≥ 1,

∀j ∈ J,

(2.1)

x ≥ 0.
We can also write the dual of CLP (τ ) as follows.
X
X
max
zj −
yi
j∈J

yi ≥

X

j∈C

i∈M

zj ,

∀i ∈ M and C ∈ C(i, τ ),

(2.2)

y, z ≥ 0.

Let τ ∗ be the smallest value of τ for which CLP (τ ) is feasible. We refer to τ ∗ as the value of
the Conﬁguration LP. Observe that τ ∗ is a lower bound on OPT. As pmax = 1, τ ∗ must be at least 1.

3

The (1, ǫ) Case

Let 0 < ǫ < 1. In the (1, ǫ)-case of restricted assignment makespan minimization, jobs
j ∈ J have one of only two possible sizes: 1 or ǫ. We partition the jobs accordingly into the sets
∆
∆
Jb = {j ∈ J | pj = 1} and Js = J \ Jb , which we will refer to as the sets of big and small jobs
respectively.
For the rest of the section ﬁx some 0 < ǫ < 1 and ζ > 0. As ǫ and ζ are ﬁxed constants,
we refer to R(ǫ, ζ) as simply R. To prove Theorem 1.1 we describe an algorithm that terminates
in polynomial time with a schedule of makespan at most τ ∗ + R for the given instance I. This
algorithm, described in Section 3.2, is a local search algorithm which continually increases the size
of a partial schedule.
5

Definition 3.1 (Partial schedule). A partial schedule is a map σ : J 7→ M ∪ {TBD} such that
(a) ∀ i ∈ M , pi (σ −1 (i)) ≤ τ ∗ + R,
(b) Jb ⊆ σ −1 (M ), and
(c) ∀ i ∈ M , |σ −1 (i) ∩ Jb | ≤ 1.
The size of a partial schedule σ is |σ −1 (M )|.
Remark 3.2. Following the description and analysis of our algorithms, it will become clear that
solving the Conﬁguration LP on the input instance I, in order to determine τ ∗ , is not necessary.
For the moment, however, it may be assumed that it is somehow known. We remark that τ ∗ can
be computed in polynomial time upto any desired accuracy ν > 0 by using the ellipsoid algorithm
with an appropriate separation oracle [BS06].
Of course, a partial schedule σ of size |J| is a schedule of makespan at most τ ∗ + R for our
instance I. The following statement ensures that partial schedules exist in the ﬁrst place.
Lemma 3.3. Suppose 1 ≤ τ ∗ < 2. Then, there is a map from Jb to M such that i) no two big jobs
are mapped to the same machine, and ii) every big job j ∈ Jb is mapped to a machine ij ∈ M such
that ij ∈ Γ(j). Furthermore, such a map can be computed in polynomial time.

3.1

Flow Networks for Job Relocations

Let σ be some partial schedule. We now deﬁne several quantities whose description depends on σ.
Definition 3.4 (Job Assignment Graphs). Gσ = (M ∪ J, E) is a directed bipartite graph with
machines and jobs in I as vertices. The edge set of Gσ is deﬁned as
∆

E = {(i, j) | ∃ i ∈ M, j ∈ J : σ(j) = i} ∪ {(j, i) | ∃i ∈ M, j ∈ J : σ(j) 6= i, i ∈ Γ(j)}.
∆

We deﬁne the graph of small job assignments Gsσ = Gσ \ Jb and the graph of big job assignments
∆

Gbσ = Gσ \ Js .

∆

∆

Definition 3.5 (Big and Small Machines). Let Mσb = {i ∈ M | σ −1 (i) ∩ Jb 6= ∅} and Mσs = M \ Mσb ,
which we refer to as big machines and small machines respectively.
We need to deﬁne two ﬂow networks which will facilitate the movement of the two kinds of jobs
we have in our instance I. We will speak of the maximum ﬂow in these ﬂow networks, even though
it may not necessarily be unique. In such cases it is implicitly assumed that there is ﬁxed rule to
obtain a particular maximum ﬂow given a ﬂow network. We also assume that ﬂow decompositions
of ﬂows in such networks contain only source to sink paths (no cycles). First, we deﬁne the ﬂow
network for big jobs.
Definition 3.6 (Flow Network for Big Jobs). For collections of machines S ⊆ Mσb , and T ⊆ Mσs ,
the ﬂow network Hσb (S, T ) is deﬁned on the directed graph Gbσ as follows. Each machine to job arc
has a capacity of 1 whereas all other arcs have inﬁnite capacity. S and T are the sources and sinks
respectively in this ﬂow network. Sinks have vertex capacities of 1. The value of maximum ﬂow in
this ﬂow network is denoted as |Hσb (S, T )|.
6

The interpretation of the ﬂow network Hσb (S, T ) is that it allows us to compute the maximum
number of vertex disjoint paths in the graph Gbσ between the sets of vertices S and T .
Proposition 3.7. For any S ⊆ Mσb and T ⊆ Mσs , there are |Hσb (S, T )| vertex disjoint paths in Gbσ
with sources in S and sinks in T .
These vertex disjoint paths suggest an update of the partial schedule σ in the natural way.
Algorithm 3.1 formalizes the description of this task and Proposition 3.8 follows easily.
Algorithm 3.1 BigUpdate(σ, X): Update σ using ﬂow paths in X.
Require: σ is a partial schedule and X is a ﬂow in Hσb (Mσb , Mσs ) where
∀f ∈ X,

p(σ −1 (f ∩ Mσs )) ≤ τ ∗ + R − 1.

P ← Vertex disjoint paths corresponding to X as ensured by Proposition 3.7.
for all p = i0 , j0 , . . . , jkp −1 , ikp ∈ P do
for ℓ = 0, . . . , kp − 1 do
σ(jℓ ) ← iℓ+1 .
end for
end for
return σ.
Proposition 3.8. For any partial schedule σ, and flow X in Hσb (Mσb , Mσs ) such that ∀f ∈ X,
p(σ −1 (f ∩ Mσs )) ≤ τ ∗ + R − 1, BigUpdate(σ, X) returns a partial schedule σ ′ such that
(a) σ ′−1 (M ) = σ −1 (M ), and
(b) ∀f = i0 , j0 , . . . , jk−1 , ik ∈ X, σ ′−1 (i0 ) ∩ Jb = ∅.
Now we deﬁne the ﬂow network for small jobs.
Definition 3.9 (Flow Network for Small Jobs). For two disjoint collections of machines S ⊆ Mσs
and T ⊆ M , the ﬂow network Hσs (S, T ) is deﬁned on the directed graph Gsσ as follows. The arcs
going from machines to jobs have capacity ǫ while arcs going from jobs to machines have inﬁnite
capacity. S and T are the sources and sinks respectively in this ﬂow network. The sinks have vertex
capacities are set as follows:
(
1 + τ ∗ + R − p(σ −1 (i)) − ǫ, if i ∈ Mσb ,
∀i ∈ T, c(i) =
τ ∗ + R − p(σ −1 (i)),
else.
The value of the maximum ﬂow in this network is denoted as |Hσs (S, T )|.
By construction it is clear that the maximum ﬂow in both ﬂow networks (3.6) and (3.9) is ﬁnite.
By the max-ﬂow min-cut theorem, inﬁnite capacity arcs going from the source-side to the sink-side
will therefore not cross any minimum capacity. We will use this fact later in our proof.
Algorithm 3.2 interprets ﬂows in Hσs (S, T ) as a collection of updates for σ. Proposition 3.10 is a
statement about the partial schedule σ ′ output by SmallUpdate(. . .), and the ﬂow X ′ computed
at the end of the while loop in the procedure. For convenience we let f source and f sink denote the
source and sink vertices, respectively, of a ﬂow path f .
7

Algorithm 3.2 SmallUpdate(σ, S, T ): Update σ using Hσs (S, T ).
Require: σ is a partial schedule, S ⊆ Mσs , T ⊆ M \ S.
X0 ← Maximum ﬂow in the network Hσs (S, {i ∈ T | p(σ −1 (i)) ≤ τ ∗ + R − ǫ}).
X ← Augment X0 to a maximum ﬂow in the network Hσs (S, T ).
while ∃f = i0 , j0 , . . . , jkf −1 , ikf ∈ X : p(σ −1 (f sink )) ≤ τ ∗ + R − ǫ do
for ℓ = 0, . . . , kf − 1 do
σ(jℓ ) = iℓ+1 .
end for
X ← X \ {f }.
end while
return σ.
Proposition 3.10. Let S ⊆ Mσs , T ⊆ M \ S, and X be the maximum flow in Hσs (S, T ). Then,
SmallUpdate(σ, S, T ) returns a partial schedule σ ′ and computes a maximum flow X ′ in Hσs′ (S, T )
at the end of the while loop in Algorithm 3.2 such that
(a) σ ′−1 (M ) = σ −1 (M ),
(b) ∀i ∈ S, p(σ ′−1 (i)) − ǫ · |{f ∈ X ′ | f source = i}| = p(σ −1 (i)) − ǫ · |{f ∈ X | f source = i}|, and
(c) ∀f ∈ X, p(σ ′−1 (f ∩ T )) > τ ∗ + R − ǫ.
(d) There is no path in the graph Gsσ′ from S to some machine i ∈ T such that
p(σ ′

−1

(i)) ≤ τ ∗ + R − ǫ.

Proof. The ﬁrst three properties follow directly from the updates performed in the while loop of
Algorithm 3.2. To see that X ′ is a maximum ﬂow in Hσs′ (S, T ), ﬁrst observe that for each update of
the partial schedule σ maintained by the algorithm, along some ﬂow path f ∈ X from σ (b) to σ (a)
in a single iteration of the while loop (superscripts for before and after), the graph Gsσ(a) can be
obtained from Gsσ(b) by simply reversing the directions of arcs of the ﬂow path in question. Suppose
that X is a maximum ﬂow in Hσs(b) (S, T ). By the max-ﬂow min-cut theorem, the maximum ﬂow
is associated with a minimum capacity cut of equal value, and the latter observation implies that
both the ﬂow value in X \ {f } and the corresponding cut capacity in the new network Hσs(a) (S, T ) is
less, than the ﬂow value in X and its corresponding cut capacity in Hσs(b) (S, T ), by ǫ. This implies
that X \ {f } is a maximum ﬂow in Hσs(b) (S, T ).
The ﬁnal property follows from the particular way in which the maximum ﬂow X in Hσs (S, T ) is
constructed. Note that Algorithm 3.2 ﬁrst computes a ﬂow X0 that maximizes the ﬂow to machines
in {i ∈ T | p(σ −1 (i)) ≤ τ ∗ +R−ǫ}, and then augments X0 to a maximum ﬂow in Hσs (S, T ). Suppose
to the contrary that there is a path P in Gsσ′ from S to a machine i such that p(σ ′−1 (i)) ≤ τ ∗ +R−ǫ.
We know that one can obtain Gsσ′ from Gsσ by reversing the arc directions of all the ﬂow paths in
X \X ′ i.e., the paths that were used to update the partial schedule in the while loop. So each arc in
P is either i) present in some path of X \ X ′ in the opposite direction, or ii) not present in the paths
of X \X ′ in the opposite direction and, therefore, also present in Gsσ . Now consider the residual flow
network of the ﬂow X \ X ′ in Hσs (S, T ). It is now easy to see that P is an augmenting path in this
residual ﬂow network because p(σ −1 (i)) + ǫ · |{f ∈ X \ X ′ | f sink = i}| = p(σ ′ −1 (i)) ≤ τ ∗ + R − ǫ,
and, therefore, c(i) ≥ τ ∗ + R − p(σ −1 (i)) ≥ ǫ · |{f ∈ X \ X ′ | f sink = i}| + ǫ. This, however,
contradicts the maximality of the ﬂow X0 computed in the ﬁrst step of the algorithm.
8

We now have the tools necessary to state our local search algorithm.

3.2

Flow Based Local Search

In this section we describe the local search algorithm that takes as input τ ∗ , a partial schedule σ, and
a small job j0 ∈ Js \ σ −1 (M ). It outputs a partial schedule σ ′ such that σ ′−1 (M ) = σ −1 (M ) ∪ {j0 }.
The algorithm is parameterized by three constants 0 < µ1 , µ2 , δ ≤ 1. They are deﬁned as:
∆

µ1 = min{1, ζ}/4,
∆

(3.1)

µ2 = min{δ, ζ}/4,

∆ √
3 − 2ǫ − 1 /2.
δ=

The algorithm maintains certain sets of machines in layers L0 , . . . , Lℓ throughout its execution,
where ℓ is some dynamically updated index variable that always points to the last layer. A layer
Li is a tuple (Ai , Bi ) where Ai ⊆ Mσs , and Bi ⊆ M , except L0 which is deﬁned to be ({j0 }, B0 ) for
some B0 ⊆ M . In addition to layers, the algorithm also maintains a collection of machines {Ii }ℓi=0
that will be disjoint from the machines in L≤ℓ .
We will describe the algorithm in a procedural style, and in the course of the execution the
algorithm, sets and other variables will be modiﬁed. Function calls are speciﬁed in the pseudocode
assuming call-by-value semantics. Concretely, this means that function calls have no side eﬀects
besides the assignment of the returned values at the call site. We abuse notation slightly and use
Li to also refer to Ai ∪ Bi (for i = 0, as A0 is not a set of machines, we use L0 to just mean B0 ),
so that L≤ℓ refers to a set of machines. For a subset of machines N ⊆ M we use Rσs (N ) denote the
set of all machines reachable from vertices N in the graph Gsσ . Note that N ⊆ Rσs (N ) always holds.
The description is now found in Algorithm 3.3. We refer to the while loop in Step 3 of Algorithm 3.3 as the main loop of the algorithm. Observe that, in Step 4, Algorithm 3.4 is used
a subroutine, which constructs and returns a new layer while potentially modifying the partial
schedule σ maintained by Algorithm 3.3.

3.3

Running Time Analysis
∆

The state of the algorithm is deﬁned to be the dynamic tuple S = (σ, ℓ, {Li }ℓi=0 , {Ii }ℓi=0 ) which
contains the variables and sets that are maintained by Algorithm 3.3. In the analysis it will be
useful to compare quantities before and after certain operations performed by the algorithm, and
we will consistently use S and S ′ to refer to the state of the algorithm before and after such an
operation. For example, if S and S ′ denote the states of the algorithm before Step 4 and after
Step 5 in Algorithm 3.3 respectively, then ℓ′ = ℓ + 1, Iℓ′ ′ = ∅, etc.
3.3.1

Basic Invariants of the Algorithm

By observing the description of Algorithms 3.3 and 3.4 we can conclude certain basic properties
which will come in handy when reasoning about its running time.
Proposition 3.11. Consider some state S of the algorithm.
(a) The sets in the collection {Ai }ℓi=1 ∪ {Bi }ℓi=0 ∪ {Ii }ℓi=0 are pairwise disjoint subsets of M .
9

Algorithm 3.3 LocalSearch(τ ∗ , σ, j0 ): Extend the partial schedule σ to include small job j0 .
Require: σ is a partial schedule, j0 ∈ Js \ σ −1 (M ).
s (Γ(j )).
⊲ Construction of layer L0
1: Set A0 ← {j0 }, B0 ← Rσ
0
2: Set ℓ ← 0 and I0 ← ∅.
3: while ∄ i ∈ B0 such that p(σ −1 (i)) ≤ τ ∗ + R − ǫ do
⊲ Main loop
4:
(σ, Aℓ+1 , Bℓ+1 ) ← BuildLayer(σ, {Li }ℓi=0 , {Ii }ℓi=0 ).
⊲ Construction of layer Lℓ+1
5:
Set ℓ ← ℓ + 1 and Iℓ+1 ← ∅.
6:
while ℓ ≥ 1 and |{i ∈ Aℓ | p(σ −1 (i)) ≤ τ ∗ + R − 1}| ≥ µ2 |Aℓ | do
7:
Set I ← {i ∈ Aℓ | p(σ −1 (i)) ≤ τ ∗ + R − 1}.
8:
(I0′ , . . . , Iℓ′ , X) ← CanonicalDecomposition(σ, {Li }ℓi=0 , {Ii }ℓi=0 , I).
9:
Set Ii ← Ii′ for all 1 ≤ i ≤ ℓ.
10:
if ∃ 1 ≤ r ≤ ℓ : |Ir | ≥ µ1 µ2 |Br−1 ∩ Mσb | then
11:
Choose the smallest such r.
12:
σ ← BigUpdate(σ, {f ∈ X | f ∩ Ir 6= ∅}).
13:
σ ← SmallUpdate(σ, Ar−1 , Br−1 ) unless r = 1.
14:
Br−1 ← Rσs (Ar−1 ) \ (Ar−1 ∪ L≤r−2 ∪ I≤r−2 ) unless r = 1.
15:
Discard all layers with indices greater than r − 1.
16:
Set ℓ ← r − 1.
17:
end if
18:
end while
19: end while
20: Update σ using a path from j0 to i in Gsσ where p(σ −1 (i)) ≤ τ ∗ + R − ǫ.
21: return σ.
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:

function CanonicalDecomposition(σ, {Li }ℓi=0 , {Ii }ℓi=0 , I)
Let X be the maximum ﬂow in Hσb (B0 ∩ Mσb , I≤ℓ ∪ I).
for 1 ≤ i ≤ ℓ − 1 do
Augment X to a maximum ﬂow in Hσb (B≤i ∩ Mσb , I≤ℓ ∪ I).
end for
for 1 ≤ i ≤ ℓ do
Set Ii′ to be the collection of sinks used by ﬂow paths from X with sources in Bi−1
end for
return (∅, I1′ , . . . , Iℓ′ , X).
end function

10

Algorithm 3.4 BuildLayer(σ, {Li }ℓi=0 , {Ii }ℓi=0 ): Construct and return a new layer.
1: Let S ← ∅.
2: while ∃i ∈ M : IsAddableQ(i, σ, {Li }ℓi=0 , {Ii }ℓi=0 , S) do
3:
σ ← SmallUpdate(σ, S ∪ {i}, T \ {i}) where T ← M \ (L≤ℓ ∪ I≤ℓ ∪ S).
4:
S ← S ∪ {i}.
5: end while
6: Aℓ+1 ← S.
s (A
7: Bℓ+1 ← Rσ
ℓ+1 ) \ (Aℓ+1 ∪ L≤ℓ ∪ I≤ℓ ).
8: return (σ, Aℓ+1 , Bℓ+1 ).
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

function IsAddableQ(i, σ, {Li }ℓi=0 , {Ii }ℓi=0 , S)
⊲ Decide if i can be added to S
if i 6∈ Mσs \ (L≤ℓ ∪ I≤ℓ ∪ S) then
return False.
end if
Set T ← M \ (L≤ℓ ∪ I≤ℓ ∪ S).
if |Hσb (B≤ℓ ∩ Mσb , S ∪ {i})| = |Hσb (B≤ℓ ∩ Mσb , S)| + 1 then

if |Hσs (S ∪ {i}, T \ {i})| ≥ |Hσs (S, T )| + p(σ −1 (i)) − (τ ∗ − 1 + R − δ) then
return True.
end if
end if
return False.
end function

(b) For each i = 1, . . . , ℓ, the sets Ai have not been modified since the last time Li was initialized
in some execution of Step 4 of Algorithm 3.3. Similarly, for i = 0, the sets A0 and B0 have
not been modified since the execution of Step 1.
(c) For each i ∈ B≤ℓ , p(σ −1 (i)) > τ ∗ + R − ǫ.
(d) For every j ∈ σ −1 (L≤ℓ ) ∩ Js , Γ(j) ⊆ L≤ℓ ∪ I≤ℓ .
Proof. (a) For a newly constructed layer Lℓ+1 in Step 4 of Algorithm 3.3, the sets Aℓ+1 and Bℓ+1
satisfy the properties by the construction of the set S and the setting in Step 7 Algorithm 3.4.
Further, Iℓ+1 is initialized to the empty set in Step 5 of Algorithm 3.3. In future updates
of Bℓ+1 (if any) in Step 14 of Algorithm 3.3, let S and S ′ be the states before Step 13 and
after Step 14 of Algorithm 3.3 respectively. From the description of Algorithm 3.2, we see
′
from the
that σ −1 (Ar−1 ) ⊇ σ ′−1 (Ar−1 ) = σ ′−1 (A′r−1 ), which then implies that Br−1 ⊇ Br−1
assignment in Step 14.
(b) This follows directly from the description of the algorithm.
(c) When a new layer Lℓ+1 is constructed during a call to BuildLayer(. . .), at the end of the
while loop in Step 2 of Algorithm 3.4, we show in Claim 3.19, that a maximum ﬂow X in
Hσs (S, T ) is computed where T = M \ (L≤ℓ ∪ I≤ℓ ∪ S). So we can apply Proposition 3.10(d)
and conclude that after the assignment in Step 7, there is no machine i ∈ Bℓ+1 such that
p(σ −1 (i)) ≤ τ ∗ + R − ǫ. We can argue in exactly the same way in Steps 13 and 14 of
Algorithm 3.3.
11

(d) This follows from Step 7 of Algorithm 3.4 and Step 14 of Algorithm 3.3.
Definition 3.12 (Collapsibility of a layer). Layer L0 is collapsible if there is an i ∈ B0 such that
p(σ −1 (i)) ≤ τ ∗ + R − ǫ. For ℓ ≥ 1, Lℓ is collapsible if Aℓ contains at least µ2 |Aℓ | machines i such
that p(σ −1 (i)) ≤ τ ∗ + R − 1.

Note the correspondence between Deﬁnition 3.12 and the conditions in Steps 3 and 6 of Algorithm 3.3.
Lemma 3.13. At the beginning of each iteration of the main loop of Algorithm 3.3, none of the
layers L0 , . . . , Lℓ are collapsible. In particular, for all 1 ≤ i ≤ ℓ,
|{i′ ∈ Ai | p(σ −1 (i′ )) ≤ τ ∗ + R − 1}| < µ2 |Ai |.

Proof. In the ﬁrst iteration of the main loop of the algorithm, ℓ = 0, and the statement follows from
the condition of the main loop of the algorithm. Assume the statement to hold at the beginning
of some iteration of the main loop of the algorithm with the state (σ, ℓ, {Li }ℓi=0 , {Ii }ℓi=0 ). Observe
that a new layer Lℓ+1 is created in Step 4 and it is tested for collapsibility in Step 6. Suppose that
the while loop in the latter step executes at least once (if it happens inﬁnitely many times, we
are done). Let r denote the choice made in Step 11 in the last execution of the step. The layers
L0 , . . . , Lr−2 continue to be non-collapsible by induction and Proposition 3.11(b), and layer Lr−1 is
not collapsible because execution exits the while loop.
Lemma 3.14. At the beginning of each iteration of the main loop of the algorithm, for every
0 ≤ i ≤ ℓ − 1,
|Ii+1 | < µ1 µ2 |Bi ∩ Mσb |.

Proof. The sets I0 , . . . , Iℓ maintained by the algorithm start out initialized to ∅ in Step 5 of Algorithm 3.3 when the corresponding layer is created. They are modiﬁed only within the while loop of
Step 6 of Algorithm 3.3 through the computation of the canonical decomposition and assignment
in Step 9. Within this loop, in Step 11, the smallest 1 ≤ r ≤ ℓ such that |Ir | ≥ µ1 µ2 |Br−1 ∩ Mσb | is
chosen; layers with indices greater than r − 1 are discarded in Step 15; and ℓ is set to r − 1 at the
end of the loop in Step 16. Therefore, the claim follows.
3.3.2

Maximum Flows and Canonical Decompositions

We now recall some properties about network ﬂows that will be of use later on in the proof our
main theorem. For basic concepts related to ﬂows, such as residual ﬂow networks and augmenting
paths, we refer the reader to the textbook by Cormen, Leiserson, Rivest and Stein [CLRS09].
Proposition 3.15. Let S ⊆ Mσb and T ⊆ Mσs . Let S ′ ⊆ Mσs and T ′ ⊆ M such that S ′ ∩ T ′ = ∅.

(a) Let X be the maximum flow in Hσb (S, T ) and let CX denote the minimum capacity cut corresponding to X i.e., the set of vertices reachable from S in the residual flow network of X.
Then, |Hσb (S, T ∪ {i})| > |Hσb (S, T )| for all i ∈ CX \ S.
(b) Let Y be the maximum flow in Hσs (S ′ , T ′ ) and let CY denote the minimum capacity cut corresponding to Y . For any i ∈ M \ CY such that i is not used as a sink by a flow path in Y ,
let the corresponding maximum flow in Hσs (S ′ ∪ {i}, T ′ \ {i}) be Y ′ and minimum capacity cut
be CY ′ . Then, CY ⊂ CY ′ and this inclusion is strict.
12

We state some consequences of the description of the procedure CanonicalDecomposition(. . .)
in Algorithm 3.3.
Proposition 3.16. For a given state S and I ⊆ Mσs , let (I0′ , . . . , Iℓ′ , X) be the tuple returned by
CanonicalDecomposition(σ, {Li }ℓi=0 , {Ii }ℓi=0 , I). Then, X is a maximum flow in the network
Hσb (B≤ℓ−1 ∩ Mσb , I≤ℓ ∪ I),
such that
(a) Ii′ is the collection of sinks used by flow paths from X with sources in Bi−1 for all i = 1, . . . , ℓ,
and I0′ = ∅,
′
)| = |Hσb (B≤i ∩ Mσb , I≤ℓ ∪ I)|, for all i = 0, . . . , ℓ − 1, and
(b) |Hσb (B≤i ∩ Mσb , I≤i+1
′
′ )|, for all i = 0, . . . , ℓ − 1.
(c) |Hσb (B≤i ∩ Mσb , I≤i+1
)| = |Hσb (B≤i ∩ Mσb , I≤ℓ

3.3.3

Relating Set Sizes within Layers

Lemma 3.17. Suppose that 1 ≤ τ ∗ < 2. At the beginning of each iteration of the main loop of the
algorithm, |B0 ∩ Mσb | ≥ 1.
Proof. After the execution of Step 1 of Algorithm 3.3, |A0 | = 1 and |B0 ∩ Mσb | ≥ 1. The latter
inequality follows from the feasibility of CLP (τ ∗ ) and the fact that τ ∗ + R − ǫ ≥ τ ∗ . We omit its
proof here since it is similar to Lemma 3.3. In the main loop of the algorithm, consider the ﬁrst
time (if at all) the schedule of big jobs on machines in B0 is altered in Step 12. Then it must be
that |I1 | ≥ µ1 µ2 |B0 ∩ Mσb | > 0 from Step 10. Using Proposition 3.16(b) in Step 8, X contains
a set of ﬂow paths connecting sources in B0 ∩ Mσb to I1 . Then, Proposition 3.8(b) implies that
|B0′ ∩ Mσb′ | < |B0 ∩ Mσb | after Step 12. Then, the condition of the main loop of the algorithm is no
longer satisﬁed since p(σ ′−1 (i)) ≤ τ ∗ + R − 1 ≤ τ ∗ + R − ǫ for some i ∈ B0′ . The condition of the
while loop in Step 6 is also not satisﬁed because ℓ = 0 after Step 16. Therefore, the main loop is
exited in this case.
Lemma 3.18. At the beginning of each iteration of the main loop of the algorithm, for every
1 ≤ i ≤ ℓ,
|Bi ∩ Mσb | > (δ(1 − µ2 ) − 2µ2 ) · |Ai |.
Proof. We ﬁrst prove a general claim which will then ease the proof the lemma.
Claim 3.19. The while loop in Step 2 of Algorithm 3.4 that iteratively builds S and modiﬁes σ
∆
satisﬁes the following invariant, where, T = M \ (L≤ℓ ∪ I≤ℓ ∪ S), as deﬁned in Step 3, and X denotes
the maximum ﬂow in the network Hσs (S, T ).
ǫ|X| ≥

X

i′ ∈S


p(σ −1 (i′ )) − (τ ∗ − 1 + R − δ) ,

∀f ∈ X, f sink ∈ Mσb .

13

Proof. Before the ﬁrst iteration of the while loop, S = ∅ and the statement is vacuously true.
Suppose it is true before some iteration for a set S. Let T and X be as in the claim. If i ∈ M is
chosen in Step 2 then, from the description of the procedure IsAddableQ(. . .) in Algorithm 3.4,
we can conclude that
1. i ∈ Mσs \ (L≤ℓ ∪ I≤ℓ ∪ S),
2. |Hσb (B≤ℓ ∩ Mσb , S ∪ {i})| = |Hσb (B≤ℓ ∩ Mσb , S)| + 1, and


3. |Hσs (S ∪ {i}, T \ {i})| ≥ |Hσs (S, T )| + p(σ −1 (i)) − (τ ∗ − 1 + R − δ) .

By the induction hypothesis and the ﬁrst property, i cannot be a sink of some ﬂow path in X. So,
X is a valid ﬂow in Hσs (S ∪ {i}, T \ {i}). Using the third property we therefore conclude that X
can be augmented to a maximum ﬂow X ′ in Hσs (S ∪ {i}, T \ {i}) such that
X


p(σ −1 (i′ )) − (τ ∗ − 1 + R − δ) ,
ǫ|X ′ | ≥ ǫ|X| + p(σ −1 (i)) − (τ ∗ − 1 + R − δ) ≥
i′ ∈S∪{i}

where the second inequality uses the induction hypothesis. In Step 3, a call to SmallUpdate(. . .)
is made. In this call, a maximum ﬂow in Hσs (S ∪ {i}, T \ {i}), say X̄, is computed at the beginning
of the while loop in Algorithm 3.2. By using Proposition 3.10(b), we can conclude that a partial
schedule σ ′ and a maximum ﬂow X̄ ′ in Hσs′ (S ∪ {i}, T \ {i}) are computed at the of the while loop
which satisfy the property

X 
−1
ǫ|X̄ ′ | ≥
p(σ ′ (i′ )) − (τ ∗ − 1 + R − δ) .
i′ ∈S∪{i}

Furthermore, Proposition 3.10(c) implies that f sink ∈ Mσb for all f ∈ X̄ ′ . This is because the
vertex capacities of small machine sinks i′ is deﬁned to be τ ∗ + R − p(σ ′−1 (i′ )) in Deﬁnition 3.9,
p(σ ′−1 (i′ )) > τ ∗ + R − ǫ, and ﬂow paths carry ﬂows of value ǫ.
Let L0 , . . . , Lℓ denote the set of layers at the beginning of the current iteration. Fix some
1 ≤ i ≤ ℓ. By Lemma 3.13,
|{i′ ∈ Ai | p(σ −1 (i′ )) ≤ τ ∗ + R − 1}| < µ2 |Ai |.
Now, consider the iteration (some previous one) in which Li was constructed and let σ (b)
be the partial schedule at the end of Step 6 in Algorithm 3.4 during the corresponding call to
BuildLayer(. . .). Using Claim 3.19, after the assignments in Steps 6 and 7, X is a maximum ﬂow
in Hσs(b) (Ai , Bi ) such that

X 
−1
ǫ|X| ≥
p(σ (b) (i)) − (τ ∗ − 1 + R − δ) > δ(1 − µ2 )|Ai | − 2µ2 |Ai |,
i′ ∈Ai

where we use Lemma 3.13 in the ﬁnal step along with the bound (τ ∗ − 1 + R − δ) ≤ 2. Now consider
−1
a sink f sink ∈ Mσb(b) used by some ﬂow path f ∈ X. By Proposition 3.10(c), p(σ (b) (f ∩ T )) >
τ ∗ + R − ǫ. Deﬁnition 3.9 states that the vertex capacity c(f sink ) = 1 + τ ∗ + R − p(σ ′−1 (f ∩ T )) − ǫ
since f sink ∈ Mσb(b) from Claim 3.19. Thus, c(f sink ) < 1. This proves that at the iteration in which
Li was constructed, by ﬂow conservation, |Bi ∩ Mσb(b) | > (δ(1 − µ2 ) − 2µ2 )|Ai |.
14

In the intervening iterations, the variable r in Step 11 of Algorithm 3.3 might have been chosen to
be i+1, and, therefore, |Bi ∩Mσb | may have reduced in Step 12 and |{i′ ∈ Ai | p(σ −1 (i′ )) > τ ∗ +R−1}|
may have reduced in Step 13. In such an event, all the layers following layer Li would have been
discarded in Step 15. But in our current iteration, the set of layers is L0 , . . . , Lℓ . So, it only remains
to prove that |Bℓ ∩ Mσb | > (δ(1 − µ2 ) − 2µ2 ) |Aℓ | in the current iteration after one or more events
where r was chosen to be ℓ + 1 in the intervening iterations. The claim is true in this case too by
arguing as follows. In each intervening iteration, where r was chosen to be ℓ + 1, after Step 12, the
partial schedule changes from σ (b) to σ (a) . Due to the way sink capacities were set in Deﬁnition 3.9,
the new ﬂow network Hσs(a) (Aℓ , Bℓ ) can be obtained from the old ﬂow network Hσs(b) (Aℓ , Bℓ ) by
increasing the capacities of the machines Mσb(b) \ Mσb(a) (those machines in Bℓ from which big jobs
were moved in Step 12) by ǫ. Using the same arguments as before after applying Lemma 3.13 proves
the lemma.
3.3.4

Maintaining Multiple Sets of Disjoint Paths

We now prove an invariant of Algorithm 3.3 concerning the updates performed in Step 12 through
the statement σ ← BigUpdate(σ, {f ∈ X | f ∩ Ir 6= ∅}).
Theorem 3.20. At the beginning of each iteration of the main loop of the algorithm, for every
0 ≤ i ≤ ℓ − 1,
|Hσb (B≤i ∩ Mσb , Ai+1 ∪ I≤i+1 )| ≥ |Ai+1 |.
Furthermore, at the beginning of each execution of the while loop in Step 6 of Algorithm 3.3,
for all 0 ≤ i ≤ ℓ − 1, |Hσb (B≤i ∩ Mσb , Ai+1 ∪ I≤i+1 )| ≥ |Ai+1 |.
Proof. Consider the ﬁrst statement. Before the ﬁrst iteration of the main loop, there is nothing to
prove. Assume the statement to be true at the beginning of iteration u of the main loop for some
u ≥ 1. We will now show that the statement holds at the end of iteration u as well.
Following Step 4 of iteration u, the newly created layer Lℓ+1 has the property Iℓ+1 = ∅ and
b
|Hσ (B≤ℓ ∩ Mσb , Aℓ+1 )| = |Aℓ+1 |, by the construction of set S in Step 2 of Algorithm 3.4. For
0 ≤ i ≤ ℓ − 1, the statement holds by the induction hypothesis and the fact that σ was not changed
in Step 4 of Algorithm 3.3 in a way that aﬀects the graph Gbσ (indeed, only small jobs are moved).
As in Step 5 of the algorithm, we also update ℓ to ℓ + 1 in this proof, and so we have at the end of
Step 5, for all 0 ≤ i ≤ ℓ − 1,
|Hσb (B≤i ∩ Mσb , Ai+1 ∪ I≤i+1 )| ≥ |Ai+1 |.

(3.2)

Now iteration u of the main loop could potentially involve one or more iterations of the while loop
in Step 6. If there are none, we are done using (3.2). The rest of the proof follows from Claim 3.21
which completes the induction on u, and also proves the second statement in Theorem 3.20.
Claim 3.21. At the end of the execution of some iteration of the while loop in Step 6 of Algorithm 3.3, for all 0 ≤ i ≤ ℓ − 1, |Hσb (B≤i ∩ Mσb , Ai+1 ∪ I≤i+1 )| ≥ |Ai+1 |, assuming it holds at the
beginning of the same iteration of the while loop.
Proof. Assume the statement to be true at the beginning of some iteration of the while loop in
question as stated in the hypothesis. We will now show that the statement holds at the end of that
iteration as well.
15

∆

As in Step 7, let I = {i ∈ Aℓ | p(σ −1 (i)) ≤ τ ∗ + R − 1}. In Step 8, we have the statement
(I0′ , . . . , Iℓ′ , X) ← CanonicalDecomposition(σ, {Li }ℓi=0 , {Ii }ℓi=0 , I),
′ ) which has the properties
which computes a specific maximum ﬂow X in the network Hσb (B≤ℓ−1 , I≤ℓ
′
guaranteed by Proposition 3.16. Recall that the sets Ii are precisely the sinks used by ﬂow paths
from X with sources in Bi−1 . Additionally, for the purposes of this proof, deﬁne Xi to be the set
of ﬂow paths from X that end in sinks Ii′ , for each 1 ≤ i ≤ ℓ. Observe that X = X1 ∪ · · · ∪ Xℓ . Let
r be the choice made in Step 11.
In the algorithm, in Step 12, observe that only the ﬂow paths Xr are used to modify the partial
schedule from σ to σ ′ and therefore also change the graph Gbσ to Gbσ′ . Step 13 does not alter the
set Ar−1 , even though it alters the partial schedule σ ′ by moving small jobs. Since it will not be
important to consider these updates for the proof of Claim 3.21, which is a statement about the
ﬂow network for big jobs, we simply denote by σ ′ the partial schedule at the end of this step. After
this update, all layers following layer Lr−1 are discarded in Step 15 and ℓ is updated to r − 1 in
Step 16. So, to prove Claim 3.21, we only need to verify that for all 0 ≤ i ≤ r − 2,
′
)| ≥ |Ai+1 |.
|Hσb ′ (B≤i ∩ Mσb′ , Ai+1 ∪ I≤i+1

(3.3)

Fix i for the rest of the proof. Since 0 ≤ i ≤ r − 2 ≤ ℓ − 2, we have, by hypothesis, |Hσb (B≤i ∩
Mσb , Ai+1 ∪ I≤i+1 )| ≥ |Ai+1 |. So let Y be the maximum ﬂow in Hσb (B≤i ∩ Mσb , Ai+1 ∪ I≤i+1 ), with
at least |Ai+1 | ﬂow paths. We now interpret the ﬂow paths X and Y as vertex disjoint paths in Gbσ
using Proposition 3.7.
For a collection of vertex disjoint paths P in Gbσ let SP ⊆ Mσb and TP ⊆ Mσs denote the set of
source and sink vertices respectively used by paths in P . Now, if it happens that SY ⊆ SX≤i+1 then
we are done. This is because there must be some X ′ ⊆ X≤i+1 such that X ′ has cardinality at least
|SY | = |Y | ≥ |Ai+1 |. Also, i + 1 ≤ r − 1 and therefore the paths Xr used to update the partial
schedule σ are disjoint from the paths X ′ and hence, X ′ continues to be present in the new graph
Gbσ′ following the update.
Our goal is to show this generally in Claim 3.22. Note that it immediately implies that even
after updating the partial schedule to σ ′ we will have a collection of at least |Y | ≥ |Ai+1 | many
′
vertex disjoint paths connecting the sources of Y to sinks in Ai+1 ∪ I≤i+1
in Gbσ′ . This proves (3.3)
and completes the proof of the claim.
Claim 3.22 (Source Alignment Lemma). There is a collection of vertex disjoint paths D in Gbσ such
′
that Xr ⊆ D, SY ⊆ SD\Xr , and each source in SY is connected by D to a sink in Ai+1 ∪ I≤i+1
.
Proof. Recall the two sets of disjoint paths X = X1 ∪ · · · ∪ Xℓ and Y we have deﬁned in the graph
Gbσ . Paths in Xi connect sources in Bi−1 ∩ Mσb to sinks in Ii′ , whereas paths in Y connect sources
from B≤i ∩ Mσb to sinks in Ai+1 ∪ I≤i+1 . We now describe a ﬁnite procedure which demonstrates
the existence of paths D as in the claim.

16

D ← X.
while ∃s ∈ SY \ SD do
v ← s.
while ¬(v ∈ SD ∨ v ∈ TY ) do
if there is an incoming arc of some path p ∈ D at v then
Set v to be the previous vertex along p.
else if there is an outgoing arc of some path q ∈ Y at v then
Set v to be the next vertex along q.
end if
end while
Augment D using the set of edges traversed in the above loop.
end while
return D.
Before we analyze this procedure, we wish to point out that the augmenting step is well-deﬁned.
Suppose D and Y are sets of disjoint paths before some iteration of the outer while loop; this is
clearly true before the ﬁrst iteration. Let s ∈ SY \ SD be chosen as the starting vertex for v. If
at no point during the execution of the inner while loop, the if condition was satisﬁed, then it is
trivial to see that the augmentation step is well-deﬁned since the set of edges that are traversed
in this case simply corresponds to some path y ∈ Y , whose source is s, and whose edges do not
intersect with the edges of paths from D. On the other hand, consider the ﬁrst time the if condition
is satisﬁed. From that point onwards it is easy to see that the inner loop simply traverses the edges
of some particular path x ∈ D in reverse order until it reaches the source of x, and the inner loop
terminates. Here, we made use of the induction hypothesis that D is a collection of vertex disjoint
paths. Therefore, we can conclude that the total set of edges traversed in this case are composed
of two disjoint parts: i) edges from the preﬁx of the path y ∈ Y , whose source is s, followed by ii)
edges from the preﬁx of the path x ∈ D in reverse order. Furthermore, the unique vertex, say v ∗ ,
at which the two parts have an incoming arc must be a machine vertex (since job vertices in Gbσ
have at most one incoming arc and the two parts are disjoint). Also, v ∗ ∈ Mσb since v ∗ 6∈ TY , and
the paths y and x must intersect at the unique edge e∗ = (v ∗ , j ∗ ) where j ∗ ∈ Jb : σ(j ∗ ) = v ∗ . Thus,
deleting the set of edges traversed in the second part, and adding the set of edges traversed in the
ﬁrst part corresponds to a valid augmentation of D.
We now prove that this procedure terminates after ﬁnite iterations of the outer while loop. We
claim that, in each iteration, either |SY \SD | decreases, or |SY \SD | stays the same and the quantity
∆

Q=

XX

y∈Y x∈D

N (x, y)

decreases, where N (x, y) is deﬁned as the total number of non-contiguous intersections between a
pair of paths x and y in Gbσ (see Figure 1). Consider a particular iteration of the outer loop. If
the if condition is never satisﬁed during the execution of the inner loop, then, by the arguments
above, the number of disjoint paths in D increases after the augmentation, and further the vertex
s chosen in the outer loop becomes a new source of D after the augmentation. On the other hand,
suppose that the path chosen for augmentation is composed of two parts arising from two paths
y ∈ Y and x ∈ D as argued before. Further, let sx be the source of x, and suppose that sx ∈ SY , as
otherwise, once again |SY \ SD | decreases after augmenting D. Let y ′ ∈ Y be the path with source
17

x
y

Figure 1: The number N (x, y) of non-contiguous intersections between the pair of paths x ∈ D and
y ∈ Y depicted here is 2. Arcs from Gbσ that are neither present in D nor in Y are shown in black.
P
P
′
′
sx . After augmenting
D
it
is
seen
that
′ N (x, y ) <
x∈D N (x, y ), and for all other paths
x∈D
P
P
y ′′ ∈ Y \ {y ′ }, x∈D′ N (x, y ′′ ) ≤ x∈D N (x, y ′′ ), thereby proving that the procedure eventually
terminates. For an example execution of a single iteration of the outer while loop of the procedure,
see Figure 2.
At the end of the procedure, we have SY ⊆ SD . As SY ⊆ B≤i , by the invariant of the procedure
′
.
that we prove below in Claim 3.23, the paths in D with sources SY end in sinks from Ai+1 ∪ I≤i+1
Also, by Claim 3.23, Xr ⊆ D (because D3 = X≥i+2 ⊇ Xr ) and SY ⊆ SD\Xr (because B≥i+1 ⊇
SD3 ⊇ SXr ), which proves the claim.
Claim 3.23 (The D Invariant). D is a collection of vertex disjoint paths in Gbσ which can be partitioned into D1 ∪ D2 ∪ D3 such that:
′
(a) SD1 ⊆ B≤i , TD1 = I≤i+1
,

(b) SD2 ⊆ B≤i , TD2 ⊆ Ai+1 , and
(c) D3 = X≥i+2 .
Proof. Before the ﬁrst iteration of the algorithm, D is initialized to X≤ℓ and therefore admits the
decomposition into D1 = X≤i+1 , D2 = ∅, D3 = X≥i+2 which satisfy all of the above invariants.
Notice here that i ≤ r − 2 ≤ ℓ − 2, so that this decomposition is well-deﬁned.
Assume the D invariant to hold for a collection of disjoint paths D at the beginning of some
iteration of outer while loop. Following the augmentation let D ′ be the resulting collection of

18

y 00

v∗

y0

sy 2 S Y n S D

sx

Figure 2: There are three blue paths y, y ′ , y ′′ ∈ Y and one red path x ∈ D shown here. Starting
from the vertex sy ∈ SY \ SD , the outer while loop of the procedure deﬁned in Claim 3.22 traverses
precisely the arcs which are dot-dashed and ends in sx , the source vertex of x, which in this case is
the same as the source vertex of y ′ and therefore sx ∈ SY .
disjoint paths. Let
∆

′
D1′ = {p ∈ D ′ | T{p} ⊆ I≤i+1
},
∆

D2′ = {p ∈ D ′ | T{p} ⊆ Ai+1 },
∆

′
}.
D3′ = {p ∈ D ′ | T{p} ⊆ I≥i+2

First we prove that D1′ , D2′ , D3′ deﬁnes a valid partition of D ′ . As it is clear that the sets
′ . Recall that the augmenting path
are disjoint, we only need to prove that TD′ ⊆ Ai+1 ∪ I≤ℓ
either ends in a source vertex of D or a sink vertex of Y . In the ﬁrst case, no new sinks are
′ . In the second case, the augmenting path ends in a sink
introduced, i.e., TD′ = TD ⊆ Ai+1 ∪ I≤ℓ
′
from SY ⊆ Ai+1 ∪ I≤i+1 . Potentially this could introduce a sink from the set I≤i+1 \ I≤i+1
. But
′
ℓ
in this case the computed canonical decomposition {Ii }i=0 would not be maximal since we now
′
have a collection of |I≤i+1
| + 1 vertex disjoint paths in D ′ with sources from B≤i and sinks in
′
′
I≤i+1 ∪ I≤i+1 ⊆ I≤ℓ ∪ I. That is, this contradicts the fact that |Hσb (B≤i , I≤i+1
)| = |Hσb (B≤i , I≤ℓ ∪ I)|
guaranteed by Proposition 3.16(b).
In the remainder of the proof we show that the deﬁned partition of D ′ satisﬁes the invariants.
Since we do not lose any sinks in the augmentation of D to D ′ , by a basic property of ﬂow augmen′
′
′
tation, it is true that |D1′ | = |I≤i+1
|, and therefore TD1′ = I≤i+1
. Next, TD2′ ⊆ Ai+1 and TD3′ ⊆ I≥i+2
follow by deﬁnition.
Since the path used to augment D started from a vertex in SY \SD and SY ⊆ B≤i it is clear that
SD1′ , SD2′ ⊆ B≤i unless we encountered a path from D3 during the augmentation process. However,
19

that would lead to a contradiction to the property of the canonical decomposition I1′ ∪ · · · ∪ Iℓ′ that
′ )| (note here again that i+1 ≤ r −1 ≤ ℓ−1) by Proposition 3.16(c).
′
)| = |Hσb (B≤i , I≤ℓ
|Hσb (B≤i , I≤i+1
Therefore, we also have that SD1′ , SD2′ ⊆ B≤i . Finally, since we did not encounter any edges of D3
during the augmentation process, we not only have that SD3′ ⊆ B≥i+1 but that D3 = D3′ .

3.3.5

Proportionally Many Options for Big Jobs

Theorem 3.24. Suppose that 1 ≤ τ ∗ < 2. At the beginning of each iteration of the main loop of
the algorithm, for every 0 ≤ i ≤ ℓ − 1,
|Ai+1 | ≥ µ1 |B≤i |.
The statement also holds at the beginning of each iteration of the while loop of Step 6 of Algorithm 3.3.
Proof. Let L0 , . . . , Lℓ be the set of layers maintained by the algorithm at the beginning of iteration
of the main loop. It is suﬃcient to prove that following the construction of layer Lℓ+1 in Step 4 of
Algorithm 3.3,
|Aℓ+1 | ≥ µ1 |B≤ℓ |.
The rest follows by applying Proposition 3.11(b). Suppose that the set S at the end of the while loop
in Step 2 of Algorithm 3.4 is smaller than µ1 |B≤ℓ |. We now describe an assignment of values to the
variables (y, z) from the dual of CLP (τ ∗ ) (deﬁned in Section 2.2) in four parts.
we will show
P Then,P
that the ﬁnal setting of dual variables (ȳ, z̄) obtained in this way satisﬁes j∈J z̄j − i∈M ȳi > 0,
while also respecting the constraints of (2.2). It then follows that the dual of CLP (τ ∗ ) is unbounded
because for any λ > 0, (λȳ, λz̄) is a feasible dual solution as well. Therefore, by weak duality,
CLP (τ ∗ ) must be infeasible, a contradiction. We now proceed to execute this strategy.
Part I: Layers We set positive dual values to all machines that appear in the sets L≤ℓ ∪ I≤ℓ , and
the corresponding jobs, as follows:

−1
(

R − δ, ∃i ∈ L≤ℓ : j ∈ σ (i) ∩ Jb ,
τ ∗ , i ∈ L≤ℓ ∪ I≤ℓ ,
(1)
(1)
zj = ǫ,
yi =
∃i ∈ L≤ℓ : j ∈ σ −1 (i) ∩ Js ,

0,
else.

0,
else.

The objective function of the assignment (y (1) , z (1) ) can be lower bounded as:
X (1) X (1)
zj −
yi ≥ (2R − δ − ǫ − 1)|B≤ℓ | − τ ∗ |I≤ℓ | − (1 − µ2 )(1 − R)|A≤ℓ | − µ2 τ ∗ |A≤ℓ |.
j∈J

i∈M

Let us explain the lower bound. For each machine i ∈ B≤ℓ , p(σ −1 (i)) > τ ∗ + R − ǫ from PropoP
(1)
(1)
sition 3.11(c). This allows us to derive j∈σ−1 (i) zj − yi > τ ∗ + R − ǫ − (1 − (R − δ)) − τ ∗ =
P
(1)
(1)
2R−δ −ǫ−1. For the machines i ∈ I≤ℓ , we have the trivial lower bound j∈σ−1 (i) zj −yi ≥ −τ ∗ .
P
(1)
(1)
Next, for each machine i ∈ A≤ℓ such that p(σ −1 (i)) > τ ∗ − 1 + R, we have j∈σ−1 (i) zj − yi ≥
20

(CX [ Mσs ) n (M (1) [ S)
e
S
i
CX

B≤` \ Mσb

Figure 3: The cut CX arising from the ﬂow X, whose paths are colored red, in the ﬂow network
Hσb (B≤ℓ ∩ Mσb , S) is shown here. All machines except those inside dotted circles are big machines.
Every big machine is matched to a distinct big job except for the machine with the outgoing
machine-job arc e, which crosses CX . The matching edges are dot-dashed and i has unit capacity.
τ ∗ − 1 + R − τ ∗ = −1 + R, whereas for the rest of the machines in A≤ℓ , we use the trivial lower
bound −τ ∗ . Thus, using Lemmas 3.13 and 3.14, we have
X (1) X (1)
zj −
yi ≥ (2R − δ − ǫ − 1 − τ ∗ µ1 µ2 ) |B≤ℓ | − (1 − µ2 )(1 − R)|A≤ℓ | − µ2 τ ∗ |A≤ℓ |. (3.4)
j∈J

i∈M

(1)

At this point we have assigned a positive zj value to big jobs j assigned by σ to machines in
L≤ℓ . However there could potentially be machines i ∈ M \ (L≤ℓ ∪ I≤ℓ ) such that i ∈ Γ(j) as well.
Therefore, the current assignment (y (1) , z (1)
solution
P) does not necessarily constitute a dual feasible
∗
since it might violate the inequality yi ≥ j∈C zj , for a conﬁguration C = {j} ∈ C(i, τ ) consisting
∆

of a single big job. We now ﬁx this in the next part. For convenience, let M (1) = L≤ℓ ∪ I≤ℓ .

Part II: Approximate Matchings Consider the ﬂow network of big jobs Hσb (B≤ℓ ∩ Mσb , S) that
was used to construct the set S. By the construction of the set S in the algorithm, there is a ﬂow
X in this network of value |S|. This ﬂow naturally deﬁnes a minimum capacity cut: the cut CX
is deﬁned as the set of reachable jobs and machines from B≤ℓ ∩ Mσb in the residual flow network
∆

corresponding to X in Hσb (B≤ℓ ∩ Mσb , S). Let M (2) = (CX ∩ Mσb ) \ M (1) . We extend the assignment
(y (1) , z (1) ) described in the ﬁrst part in the following way.
(
(
R − δ, ∃i ∈ M (2) : j ∈ σ −1 (i) ∩ Jb ,
R − δ, i ∈ M (2) ,
(2)
(2)
zj =
yi =
0,
else.
0,
else.

The capacity of the cut CX is |S| by the max-ﬂow min-cut theorem. This in particular implies that
no job-machine arcs can cross this cut as such arcs have inﬁnite capacity. In other words, the only
arcs crossing CX are machine-job arcs and machine-supersink arcs where the machine arises from
S (recall that sink vertices have vertex capacity 1 in Hσb (B≤ℓ ∩ Mσb , S) according to Deﬁnition 3.6).
21

ρ ← σ.
U ← S.
V ← M \ (M (1) ∪ U ).
Y ← Maximum ﬂow in Hσs (U, V ).
CY ← Mincut corresponding to Y in Hσs (U, V ).
while ∃ i ∈ (CX ∩ Mρs ) \ (M (1) ∪ CY ) do
Augment Y to a maximum ﬂow in Hρs (U ∪ {i}, V \ {i}).
⊲ This is well-deﬁned
s
CY ← Mincut corresponding to Y in Hρ (U ∪ {i}, V \ {i}).
for f ∈ Y : the sink of f belongs to ((CX ∩ Mρs ) \ (M (1) ∪ CY )) do
Update ρ by using the ﬂow path f .
Y ← Y \ {f }.
end for
⊲ CY is still the mincut corresponding to Y
U ← U ∪ {i}.
V ← V \ {i}.
end while
return CY
Figure 4: Mincut Growing Procedure
For every big machine i that is present in CX , the corresponding big job assigned to i by σ is
also present in CX with the exception of at most |S| big jobs as shown in Figure 3 (corresponding
to the machine-job arcs that cross the cut CX ). Therefore, the total loss incurred in this step is at
most |S|. In other words,
X (2) X (2)
zj −
yi ≥ −(R − δ)|S|.
(3.5)
j∈J

i∈M

Part III: Growing Mincuts In this part and the next, we assign positive dual values to machines
in S, machines in (CX ∩ Mσs ) \ M (1) , and some other machines, to complete the description of our
dual assignment. To make such an assignment, we will use the algorithm described in Figure 4 in
the analysis.
The properties of the above procedure that we require in the proof are encapsulated in the
following claim which we will prove inductively.
Claim 3.25. The while loop of the above procedure maintains the following invariants.
(a) ρ is a partial schedule.
(b) Y is a maximum ﬂow in Hρs (U, V ) and CY is the corresponding mincut.
(c) The value of maximum ﬂow Y can be upper bounded as
X
|Hρs (U, V )| ≤ (τ ∗ + R)|S| +
(p(ρ−1 (i)) − (τ ∗ − 1 + R − δ)).
i∈U \S

(d) There is no ﬂow path f ∈ Y that ends in a sink belonging to (CX ∩ Mρs ) \ (M (1) ∪ CY ).
(e) For each i ∈ (CX ∩ Mρs ) \ (M (1) ∪ CY ),
|Hρs (U ∪ {i}, V \ {i})| < |Hρs (U, V )| + (p(ρ−1 (i)) − (τ ∗ − 1 + R − δ)).
22

CY 0

g Y 00
C Ys

P
i0

i

CX
I = (CX \ Mρs0 ) n (M (1) [ CY 0 )
0 ∆

Figure 5: The induction step in the proof of Claim 3.25. For an i ∈ (CX ∩ Mρss ) \ (M (1) ∪ CYs ), Y ′ is
the maximum ﬂow in Hρss (Us ∪{i}, Vs \{i}) shown in blue. It is partitioned as Y ′′ ∪P . The direction
of the arcs in P is reversed, as shown in red, during the for loop from the procedure deﬁned in Part
III. The mincuts corresponding to the ﬂows Y ′ and Ys obey the inclusion CY ′ ⊃ CYs .
Proof. Before the ﬁrst iteration of the while loop, Claim 3.25(c) is satisﬁed because U = S and ρ = σ
is a partial schedule; Claim 3.25(d) is satisﬁed because Y is a ﬂow that has the properties guaranteed
by Claim 3.19; Claim 3.25(e) follows from the fact that the while loop in Step 2 of Algorithm 3.4 was
exited. The last claim needs some more explanation. Note that every i ∈ (CX ∩ Mσs ) \ (M (1) ∪ CY )
satisﬁes the following two properties:
• i ∈ Mσs \ (L≤ℓ ∪ I≤ℓ ∪ S), and
• |Hσb (B≤ℓ ∩ Mσb , S ∪ {i})| = |Hσb (B≤ℓ ∩ Mσb , S)| + 1.
The second property follows from Proposition 3.15(a) because i ∈ CX . Therefore, for all such i, it
must be the case that Hσs (S ∪ {i}, T \ {i}) < Hσs (S, T ) + p(σ −1 (i)) − (τ ∗ − 1 + R − δ) .
Suppose that the statement is true until the beginning of some iteration of the while loop. Let
Ys be the maximum ﬂow in Hρss (Us , Vs ) and CYs be the corresponding minimum cut maintained by
this procedure. We now show it holds at the end of that iteration as well. Let the machine chosen in
this iteration be i ∈ (CX ∩Mρss )\(M (1) ∪CYs ). The augmentation step is well deﬁned because Ys is a
ﬂow in Hρss (Us , Vs ) that does not use any ﬂow path with a sink belonging to (CX ∩Mρss )\(M (1) ∪CYs )
as guaranteed by Claim 3.25(d). Therefore, Ys is also a feasible ﬂow in Hρss (Us ∪ {i}, Vs \ {i}), which
can be augmented to a maximum ﬂow in that network, say Y ′ . Let CY ′ be the corresponding mincut
that is computed in the procedure. We remark that CYs ⊂ CY ′ where the inclusion is strict, because
i ∈ CY ′ \ CYs , which follows from Proposition 3.15(b). We use this fact later.
The execution now enters a for loop that modiﬁes the ﬂow Y and the partial schedule ρ maintained by the procedure, which currently assume the values Y ′ and ρs respectively. Let Y ′′ ⊆ Y ′
∆
and ρ′ be the state of Y and ρ at the end of the for loop respectively, so that P = Y ′ \ Y ′′ is
precisely the set of ﬂow paths used to update the partial schedule ρ maintained by the procedure. It
is seen that the Gsρ′ is obtained from the graph Gsρs by reversing the directions of the arcs contained
in the paths of P . For an illustration, see Figure 5.
23

As only ﬂow paths P ⊆ Y ′ ending in small machine sinks were used to update ρ, ρ′ is still
a partial schedule (recall that Y ′ is a ﬂow in the network Hρss (Us ∪ {i}, V \ {i})), which proves
Claim 3.25(a). We also claim that Claim 3.25(b) holds.
Claim 3.26. Y ′′ is a maximum ﬂow in Hρs′ (Us ∪ {i}, Vs \ {i}) and CY ′ is the corresponding minimum
cut.
Proof. The ﬁrst part is true, because, after every single iteration of the for loop, the value of the
ﬂow Y decreases by ǫ and so does the capacity of the arcs in Hρs (U ∪ {i}, V \ {i}) crossing the cut
CY ; since the value of the ﬂow Y ′ was equal to the capacity of the minimum cut CY ′ before the for
loop, by the max-ﬂow min-cut theorem, the claim follows (we apply the converse of the max-ﬂow
min-cut theorem at the end).
The second part is true as well, because the set of vertices reachable from Us ∪ {i} in the reduced
ﬂow network corresponding to the ﬂow Y ′ in Hρss (Us ∪ {i}, Vs \ {i}) (deﬁned to be CY ′ ) is the same
as the set of vertices reachable from Us ∪ {i} in the reduced ﬂow network corresponding to the ﬂow
Y ′′ in Hρs′ (Us ∪ {i}, Vs \ {i}).
Next, using Claims 3.25(e) and 3.25(c), we see that
(i)) − (τ ∗ − 1 + R − δ))
|Hρss (Us ∪ {i}, Vs \ {i})| < |Hρss (Us , Vs )| + (p(ρ−1
| s
{z
}
(∗)

≤ (τ ∗ + R)|S| +

= (τ ∗ + R)|S| +

X

i′ ∈Us \S

′
∗
(p(ρ−1
s (i )) − (τ − 1 + R − δ)) + (∗)

X

i′ ∈(Us ∪{i})\S

′
∗
(p(ρ−1
s (i )) − (τ − 1 + R − δ)).

In the ﬁnal equality, note that i 6∈ S because i 6∈ CY ′ and CY ′ ⊇ Us ⊇ S (using the fact mentioned
in our earlier remark). In each iteration of the for loop, we saw that the value of the quantities
|Hρs (U ∪ {i}, V \ {i})| and p(ρ−1 (i)) reduces exactly by ǫ so that at the end of the for loop, we have
|Hρs′ (Us ∪ {i}, Vs \ {i})| ≤ (τ ∗ + R)|S| +

X

i′ ∈(Us ∪{i})\S

(p(ρ′−1 (i′ )) − (τ ∗ − 1 + R − δ)),

which proves Claim 3.25(c).
At the end of the for loop, Claim 3.25(d) is true as well because for every f ∈ Y ′′ the sink of
∆

f does not belong to I ′ = (CX ∩ Mρs′ ) \ (M (1) ∪ CY ′ ) by the postcondition of the loop, and using
Claim 3.26. It only remains to prove Claim 3.25(e). Suppose towards contradiction that there is an
i′ ∈ I ′ such that
|Hρs′ (Us ∪ {i, i′ }, Vs \ {i, i′ })| ≥ |Hρs′ (Us ∪ {i}, Vs \ {i})| + (p(ρ′

−1

(i′ )) − (τ ∗ − 1 + R − δ)).

Let F be some maximum ﬂow in Hρs′ (Us ∪ {i, i′ }, Vs \ {i, i′ }) obtained by augmenting Y ′′ (which is
well-deﬁned because Y ′′ does not have ﬂow paths that use vertices in I ′ as sinks). Construct a new
ﬂow network H ′ from Hρss (Us ∪ {i, i′ }, Vs \ {i, i′ }) by adding a copy of the vertex i′ and call it i′dummy
(with identical neighborhood structure and vertex capacity). Interpret the ﬂow P in H ′ so that
none of the ﬂow paths use i′ as as sink (they may use i′dummy however). In the residual flow network
corresponding to this ﬂow in H ′ , use the ﬂow paths of F to augment the ﬂow. This is well-deﬁned
24

because of the way the graphs Gsρ′ and Gsρs are related (recall that, to obtain the former from the
latter, we just need to reverse the directions of the arcs of paths in P ). It is important to note here
that the resulting ﬂow only contains paths and no cycles. Through this process we obtain a ﬂow of
value |F | + |P | in the network H ′ . By assumption,
|F | + |P | ≥ |Y ′′ | + (p(ρ′
|
′

= |Y | + (∗)

−1

(i′ )) − (τ ∗ − 1 + R − δ)) +|P |
{z
}
(∗)

= |Ys | + fi + (∗).
The ﬁrst equality follows from the deﬁnition of P ; the second equality follows from the fact that Ys
was augmented in the ﬂow network |Hρss (Us ∪ {i}, Vs \ {i})| to Y ′ so that Y ′ has exactly fi value
ﬂow paths with sources at i, and |Ys | value ﬂow paths with sources in Us (here we make use of the
fact that Ys is a maximum ﬂow). Therefore, we have a ﬂow of value at least |Ys | + fi + (∗) in the
network H ′ . Since the latter ﬂow was constructed by augmenting maximum ﬂows, we can deduce
that the it is composed of |Ys | value ﬂow paths originating at Us , fi value ﬂow paths originating at
i and the rest originating at i′ . Deleting all ﬂow paths leading to i′dummy , we have a resulting ﬂow
of value at least |Ys | + fi + (∗) − li′ , where li′ is the value of ﬂow paths in P that end in i′ . Owing
′
to the way in which we updated ρ in the for loop, we can see that li′ = p(ρ′−1 (i′ )) − p(ρ−1
s (i )).
−1
′
∗
Therefore there is a ﬂow of value at least |Ys | + (p(ρs (i )) − (τ − 1 + R − δ)) in the network
Hρss (Us ∪ {i′ }, Vs \ {i′ }), which then implies
|Hρss (Us ∪ {i′ }, Vs \ {i′ })| ≥ |Hρss (Us , Vs )| + (p(ρs −1 (i′ )) − (τ ∗ − 1 + R − δ)),
contradicting Claim 3.25(e).
Returning to our proof, we now run this procedure with one modiﬁcation: we add i to the set
U maintained by the procedure only if, in addition to the condition in the while loop, the new set
CY′ would have a size at least |CY | + 2. Let ρf and CY,f be the reallocation policy and the cut at
the end of the exeuction of this modiﬁed procedure. We have as a postcondition that executing the
body of the while loop once with an i ∈ (CX ∩ Mρsf ) \ (M (1) ∪ CY,f ) would result only in a set of
size |CY,f | + 1 (note that i would be the new element in that case). Extend the dual assignment as
follows.
(
(
∗,
ǫ, j ∈ ρ−1
τ
i
∈
C
,
Y,f
(3)
(3)
f (i) ∩ Js : i ∈ CY,f ,
zj =
yi =
0,
else.
0, else.
We now need to bound the total loss incurred in this part of the proof. Suppose the while
loop in the procedure executes t ≥ 0 times. Let Uf , Vf , and Yf be the state of the (remaining)
variables at the end of the procedure. For convenience assume that Uf = S ∪ {i1 , . . . , it }, where the
numbering follows the order in which the machines are added to the variable U in the while loop.
By Claim 3.25(b), Yf is a maximum ﬂow in Hρsf (Uf , Vf ) and CY,f is the corresponding mincut.
∆

∆

Let P = (CY,f \ Uf ) ∩ Mρsf and Q = CY,f ∩ Mρbf . Since the size of the mincut in the variable CY
increased by at least 2 in each iteration, we have at the end that |P | + |Q| ≥ t.
By the max-ﬂow min-cut theorem, the value of the maximum ﬂow equals the capacity of the

25

minimum cut, and therefore, by Claim 3.25(c),
t
X
∗
(p(ρ−1
(τ + R)|S| +
f (ij )) − (τ − 1 + R − δ))
∗

j=1

X

>

ci +

X
X
(τ ∗ + 1 + R − p(ρ−1
(τ ∗ + R − p(ρ−1
f (i)) − ǫ),
f (i))) +
i∈Q

i∈P

i∈S∪{i1 ,...,it }∪P ∪Q

where ci is the total capacity of machine-job arcs with i as one endpoint crossing the minimum cut
CYf . The terms on the left together upper bound the value of maximum ﬂow in the ﬁnal network
Hρsf (Uf , Vf ), whereas the terms on the right count the contributions to the minimum cut arising
from machine-job arcs and machine-sink arcs. Splitting the ﬁrst sum on the right,
t
X
∗
(p(ρ−1
(τ + R)|S| +
f (ij )) − (τ − 1 + R − δ))
∗

j=1

>

X

ci +

i∈S

X

ci +

i∈{i1 ,...,it }∪P

X

ci +

i∈Q

X
X
(τ ∗ + 1 + R − p(ρ−1
(τ ∗ + R − p(ρ−1
f (i)) − ǫ).
f (i))) +
i∈Q

i∈P

After rearranging the terms,
(τ ∗ + R)|S| − t(τ ∗ − 1 + R − δ) >

X
i∈S

ci −

X

i∈{i1 ,...,it }∪P

(p(ρ−1
f (i)) − ci )

X
∗
−
(p(ρ−1
f (i)) − 1 − ci ) + (|P | + |Q|)(τ + R) − |Q|ǫ,
i∈Q

we derive
X
−
ci +
i∈S

X

i∈{i1 ,...,it }∪P

(p(ρ−1
f (i)) − ci ) +

X
(p(ρ−1
f (i)) − 1 − ci )
i∈Q

> −(τ ∗ + R)|S| + t(τ ∗ − 1 + R − δ) + (|P | + |Q|)(τ ∗ + R) − |Q|ǫ

≥ −(τ ∗ + R)|S| + t(τ ∗ − 1 + R − δ) + (|P | + |Q|)(τ ∗ + R − ǫ).
(3.6)
We demonstrate that the assignment (y (3) , z (3) ) amortizes itself locally using (3.6).

26

X (3) X (3)
zj −
yi
j∈J

i∈M

X

=

i∈S∪{i1 ,...,it }∪P

≥−
|

X

ci +

i∈S

(p(ρ−1
f (i)) − ci ) +
X

(p(ρ−1
f (i))

i∈{i1 ,...,it }∪P

X
i∈Q

∗
(p(ρ−1
f (i)) − 1 − ci ) − τ (|S| + t + |P | + |Q|)

− ci ) +

{z

X
i∈Q

∗
(p(ρ−1
f (i)) − 1 − ci ) −τ (|S| + t + |P | + |Q|)

}

(3.6)

> −(τ ∗ + R)|S| + t(τ ∗ − 1 + R − δ) + (|P | + |Q|)(τ ∗ + R − ǫ) − τ ∗ (|S| + t + |P | + |Q|)

= −(τ ∗ + R)|S| + t(τ ∗ − 1 + R − δ) + (|P | + |Q|)(R − ǫ) − τ ∗ (|S| + t)

= −(2τ ∗ + R)|S| + t(R − δ − 1) + (|P | + |Q|)(R − ǫ)

≥ −(2τ ∗ + R)|S| + t(R − δ − 1) + t(R − ǫ)

= −(2τ ∗ + R)|S| + t

(2R − δ − ǫ − 1)
{z
}
|

≥ 0 follows from Claim A.1
∗

≥ −(2τ + R)|S|.

(3.7)

Part IV: The Rest As noted in Part III, we may now have machines i ∈ (CX ∩Mρsf )\(M (1) ∪CY,f )
that increase the size of the set CY,f described in the previous part by one. Let M (4) denote the set
of such machines; note that they must necessarily be a subset of Mσs (which is the same as Mρsf ).
By the postcondition of the modiﬁed procedure, we deduce that each machine in M (4) has at least
τ ∗ − 1 + R − δ processing time small jobs assigned to it by ρf such that each of those jobs can be
assigned to only machines in CY,f ∪ M (1) besides itself. Let
∆

(1)
}.
Si = {j ∈ ρ−1
f (i) ∩ Js | Γ(j) ⊆ {i} ∪ CY,f ∪ M

We set the dual values of these machines as follows.
(4)

yi

=

(P
0,

j∈ρ−1
f (i)

(4)

zj ,

i ∈ M (4) ,

(4)

zj

else.

=

(

ǫ,
0,

j ∈ Si : i ∈ M (4) ,
else.

The Dual Assignment Before we describe our ﬁnal dual assignment (ȳ, z̄), let us note that the
supports of (y (1) , z (1) ), (y (3) , z (3) ) and (y (4) , z (4) ) are disjoint by construction. Further, observe that
the support of (y (2) , z (2) ) may only intersect with the support of (y (3) , z (3) ), and is disjoint from
the other two. However, we can assume without loss of generality that they too are disjoint, as
machines that receive both positive y (2) and y (3) values will only help us in the later arguments.
(3)
(2)
The reasoning is that, for a machine i such that yi = τ ∗ and yi = R − δ, we will only consider
(3)
the contribution of yi to the ﬁnal assignment ȳ in the feasibility whereas we will count both
contributions towards the objective function i.e., we prove that the dual objective function of the
ﬁnal assignment is positive even after counting an extra contribution of R − δ for such machines.
Note that there can be no jobs in the intersection of the supports of the dual assignments from the
second and third parts. So we assume that the supports of the dual assignments from the four parts
are disjoint. Set (ȳ, z̄) to be the union of the four assignments in the natural way.
27

P
∗
Feasibility Our assignment (ȳ, z̄) to the dual variables is such that
j∈C z̄j ≤ τ for every
i ∈ M, C ∈ C(i, τ ∗ ) because z̄j ≤ pj for every j ∈ J. Therefore, the constraints of (2.2) involving
machines i for which ȳi = τ ∗ are satisﬁed.
This leaves us to only consider the machines whose dual values were set in Parts II and IV.
Let i ∈ M (2) and C ∈ C(i, τ ∗ ). By Proposition 3.11(d), the construction of the cut CY,f (note
that inﬁnite capacity job-machine arcs cannot cross this cut), and the dual setting of z (4) (where
(4)
we assigned positive zj values only to jobs in Si for some i ∈ M (4) ), there can be no j ∈ C ∩ Js
such that z̄j > 0. As τ ∗ < 2, there is at most one big job in a conﬁguration. Since it is assigned
(4)
a dual value of R − δ, all constraints involving such machines are satisifed.
P Now let i ∈ M ∗ and
∗
∗
C ∈ C(i, τ ). Recall that ȳi > τ − 1 + R − δ. If C contains a big job then j∈C z̄j ≤ R − δ + τ − 1.
If C does not contain big jobs, then,
X
X
X
z̄j =
z̄j ≤
z̄j = ȳi .
j∈C

j∈C:z̄j >0

j∈σ−1 (i)

The inequality in the middle deserves explanation. This follows from the assertion that any job
j ∈ C ∩ Js such that z̄j > 0 must be part of σ −1 (i) by Proposition 3.11(d), the construction of the
cut CY,f , and the dual setting of z (4) .
P
P
Positivity Now that we have described our dual assignment, we show j∈J z̄j − i∈M ȳi > 0 by
counting the contributions to the objective function from the dual variable settings in each of the
four previous parts.
From (3.4) and (3.5), the total gain in the ﬁrst and second part is at least
(2R − δ − ǫ − 1 − τ ∗ µ1 µ2 ) |B≤ℓ | − (1 − µ2 )(1 − R)|A≤ℓ | − µ2 τ ∗ |A≤ℓ | − |S|.
In the third part, using (3.7), the total loss is at most (2τ ∗ + R)|S|. In the fourth part there is no
net loss or gain. So, we can lower bound the objective function value of our dual assignment (ȳ, z̄)
as follows, making use of Lemma 3.17 and Lemma 3.18 in the second inequality.
X
X
z̄j −
ȳi
j∈J

i∈M

≥ (2R − δ − ǫ − 1 − τ ∗ µ1 µ2 ) |B≤ℓ | − (1 − µ2 )(1 − R)|A≤ℓ | − µ2 τ ∗ |A≤ℓ | − |S| − (2τ ∗ + R)|S|

≥ (2R − δ − ǫ − 1 − τ ∗ µ1 µ2 − (1 + 2τ ∗ + R)µ1 ) |B≤ℓ | − (1 − µ2 )(1 − R)|A≤ℓ | − µ2 τ ∗ |A≤ℓ |

≥ (2R − δ − ǫ − 1 − τ ∗ µ1 µ2 − (1 + 2τ ∗ + R)µ1 ) (δ(1 − µ2 ) − 2µ2 ) · |A≤ℓ | − ((1 − µ2 )(1 − R) − µ2 τ ∗ ) |A≤ℓ |


≥ (2R − δ − ǫ − 1 − τ ∗ µ1 µ2 − (1 + 2τ ∗ + R)µ1 ) (δ(1 − µ2 ) − 2µ2 ) − (1 − µ2 )(1 − R) − µ2 τ ∗ |A≤ℓ |.
|
{z
}
(∗)

Subtituting the values of R, µ1 , µ2 , δ as deﬁned in the statement of Theorem 1.1 and (3.1), one
can verify (see Claim A.1) that the bracketed expression (∗) is strictly positive for every 1 ≤ τ ∗ < 2,
0 < ǫ < 1 and ζ > 0.

3.3.6

Polynomial Bound on Loop Iterations

Corollary 3.27. Suppose 1 ≤ τ ∗ < 2. In each execution of the while loop in Step 6 of Algorithm 3.3, the if condition in Step 10 is satisfied.
28

Proof. Consider the beginning of some iteration of the while loop in Step 6 of Algorithm 3.3 with
∆
a state S. By the condition in Step 6, ℓ ≥ 1 and |I| ≥ µ2 |Aℓ |, where I = {i ∈ Aℓ | p(σ −1 (i)) ≤
τ ∗ + R − 1}. Applying Theorem 3.20, |Hσb (B≤ℓ−1 ∩ Mσb , Aℓ ∪ I≤ℓ )| ≥ |Aℓ |. Since |I| ≥ µ2 |Aℓ | and
I ⊆ Aℓ this means that
|Hσb (B≤ℓ−1 ∩ Mσb , I ∪ I≤ℓ )| ≥ µ2 |Aℓ | ≥ µ1 µ2 |B≤ℓ−1 ∩ Mσb |,
where the second inequality follows from Theorem 3.24. By Proposition 3.16(a), at least one of
the sets Ii′ computed in Step 8 of Algorithm 3.3 must be of size at least µ1 µ2 |Bi−1 ∩ Mσb | for some
1 ≤ i ≤ ℓ.
Given the state S of the algorithm at some point during its execution, the signature of a layer
Li is deﬁned as
!
 i
k
j
1
∆
Bi ∩ Mσb
+ i,
si = log 1
1−µ1 µ2
η
∆

where η = (δ(1 − µ2 ) − 2µ2 ) µ1 > 0 by Claim A.2. The signature vector corresponding to the given
state is then deﬁned as a vector in the following way:
∆

s = (s0 , . . . , sℓ , ∞).
Lemma 3.28. Suppose 1 ≤ τ ∗ < 2. The signature vector satisfies the following properties.
(a) At the beginning of each iteration of the main loop of the algorithm, ℓ = O(log |Jb |).
(b) The coordinates of the signature vector are well-defined and increasing at the beginning of each
iteration of the main loop of the algorithm.
Proof. Consider the beginning of some iteration of the main loop of the local search algorithm. Let
L0 , . . . , Lℓ be the set of layers maintained by the algorithm. Let 0 ≤ i ≤ ℓ. Observe that from the
moment layer Li was constructed until now, Ai remains unmodiﬁed (even though the assignment
of jobs by σ to machines in Aℓ may have changed). This is because Ai can be modiﬁed only if, in
some intervening iteration of the main loop, the variable r from Step 11 of Algorithm 3.3 is chosen
to be i′ for some i′ ≤ i. But in that case we discard all the layers Li′ , . . . , Lℓ in Step 15 and this
includes layer Li as well. Therefore, for 0 ≤ i ≤ ℓ − 1,
|Bi+1 ∩ Mσb |

Lem 3.18

>

(δ(1 − µ2 ) − 2µ2 ) |Ai+1 |

Thm 3.24

≥

(∗)

(δ(1 − µ2 ) − 2µ2 ) · µ1 |B≤i | ≥ η|B≤i ∩ Mσb |.

The second inequality above uses the fact that the layers L0 , . . . , Lℓ were not modiﬁed since construction as argued previously. As the ﬁnal term in the chain of inequalities above is at least
η|Bi ∩ Mσb |, this proves (b). As the sets B0 , . . . , Bℓ are disjoint by construction,
|B≤i+1 ∩ Mσb | = |Bi+1 ∩ Mσb | + |B≤i ∩ Mσb |

Using (∗)

≥

(1 + η)|B≤i ∩ Mσb |.

As |B0 ∩ Mσb | ≥ 1 by Lemma 3.17, ℓ is O(log1+η |Mσb |) = O(log |Jb |), which proves (a).
Lemma 3.29. Suppose 1 ≤ τ ∗ < 2. Only poly(|Jb |) many signature vectors are encountered during
the execution of Algorithm 3.3.
29

Proof. By Lemma 3.28(a), and the deﬁnition of si , each coordinate is at most O(log |Jb |). Lemma 3.28(b)
also implies that the coordinates of the signature vector are increasing at the beginning of the main
loop. So every signature vector encountered at the beginning of the main loop can be unambiguously
described as a subset of a set of size O(log |Jb |).
Lemma 3.30. Suppose 1 ≤ τ ∗ < 2. The signature vector decreases in lexicographic value across
each iteration of the main loop of the local search algorithm.
Proof. Consider the beginning of some iteration of the main loop of the local search algorithm
with the state S. So, L0 , . . . , Lℓ are the set of layers at the beginning of the iteration. During
the iteration, a single new layer Lℓ+1 is created in Step 4, and zero or more layers from the set
{L1 , . . . , Lℓ , Lℓ+1 } are discarded in Step 15. We consider two cases accordingly.
• No layer is discarded. Therefore, at the end of this iteration, we will have layers L0 , . . . , Lℓ+1
and we can apply Lemma 3.28(b) at the beginning of the next iteration to prove this claim.
Note here that we used the converse of Corollary 3.27 to deduce that the while loop in Step 6
of Algorithm 3.3 did not execute since no layer was discarded.
• At least one layer is discarded. During each iteration of the while loop in Step 6, for some
1 ≤ r ≤ ℓ + 1 as chosen in Step 11, the if condition in Step 10 is satisﬁed by Corollary 3.27.
Therefore, the size of |Br−1 ∩ Mσb | reduces to at most (1 − µ1 µ2 )|Br−1 ∩ Mσb |, and the (r − 1)th coordinate of the signature vector reduces by at least one, whereas the coordinates of the
signature vector of the layers preceding r − 1 are unaﬀected. In other words, the signature
vector at the beginning of the next iteration of the main loop (if any) would be
s′ = (s0 , . . . , sr−2 , s′r−1 , ∞),
where r ≤ ℓ + 1 and s′r−1 ≤ sr−1 − 1.

An immediate corollary of Lemma 3.29 and Lemma 3.30 is that the local search algorithm
described in Section 3.2 terminates after poly(|Jb |) iterations of the main loop under the assumption
1 ≤ τ ∗ < 2. Notice, however, that all statements proved in Section 3.3.6 also hold merely given the
conclusions of Lemma 3.17 and Theorem 3.24 without necessarily assuming that τ ∗ ∈ [1, 2).

3.4

Proof of the Main Theorem

Proof of Theorem 1.1. Let I be the given instance of the (1, ǫ) case of restricted assignment
makespan minimization and OPT denote the optimum makespan. Assume for the moment that
τ ∗ is known by solving the Conﬁguration LP. If τ ∗ ≥ 2, then the algorithm of Lenstra, Shmoys and
Tardos [LST90] for this problem gives an OPT + pmax approximation guarantee, which is of course
at most 1.5OPT in this case.
Suppose instead that 1 ≤ τ ∗ < 2. Start with a partial schedule σ guaranteed by Lemma 3.3.
Let σ and j0 ∈ Js \ σ −1 (M ) denote the input partial schedule and small job to Algorithm 3.3. From
its description it is clear that the partial schedule maintained by it is modiﬁed either in Step 20 or
within the main loop. In the main loop, this occurs in exactly three places: Step 3 of Algorithm 3.4;
Steps 12 and 13 of Algorithm 3.3. From Lemma 3.29 and Lemma 3.30, we deduce that the main
30

loop is exited after poly(|Jb |) iterations. Using Proposition 3.10(a), Proposition 3.8(a), and Step 20
of the local search algorithm, the output partial schedule σ ′ therefore satisﬁes the property
σ ′−1 (M ) = σ −1 (M ) ∪ {j0 }.
Repeating this algorithm a total of |Js | times yields a schedule of makespan at most τ ∗ + R for I
in polynomial time.
However, it is not necessary to know τ ∗ in advance by solving the Conﬁguration LP. Suppose
that τ ∈ [1, 2) is a guess on the value of τ ∗ . Let A(τ ) denote the following algorithm. Run the
procedure outlined above after substituting τ in place of τ ∗ with two modiﬁcations to Algorithm 3.3:
if |B0 ∩ Mσb | = 0 after Step 1, or if |Aℓ+1 | < µ1 |B≤ℓ | in any execution of Step 4, then terminate the
procedure with an error claiming that the guessed value τ < τ ∗ .
Suppose A(τ ) returns a schedule during a binary search over the range τ ∈ [1, 2), then it is
guaranteed to have makespan at most τ + R. Note that the range of possible values for τ ∗ is discrete
(1 + kǫ or kǫ for k ∈ Z). As the running time analysis in Section 3.3.6 of Algorithm 3.3 depends
only on conclusions of Lemma 3.17 and Theorem 3.24, A(τ ) is always guaranteed to terminate in
polynomial time irrespective of whether a schedule is returned or not. If A(τ ) does not return
a meaningful result during the binary search then τ ∗ ≥ 2, and it suﬃces to return the schedule
computed by the algorithm of Lenstra et al. [LST90].

3.5

Balancing Against Bipartite Matching

The approximation guarantee of the local search algorithm from Section 3.2 deteriorates with increasing ǫ. There is however a simple algorithm that performs better for the case of large ǫ.
Theorem 3.31. Let 0 < ǫ < 1. The (1, ǫ) case of restricted assignment makespan minimization admits a 2 − ǫ approximation algorithm.
Proof. Let OPT denote the makespan of an optimum solution to the input instance. Guess OPT
through binary search. Construct a bipartite graph with ⌊OPT/ǫ − 1⌋ small nodes and 1 big node
for each machine in the input instance. Each small job is connected by an edge to all the nodes of
all the machines it can be assigned to with a ﬁnite processing time. Each big job is connected by an
edge to all the big nodes of all the machines it can be assigned to with a ﬁnite processing time. It is
easy to see that there is a perfect matching in this bipartite graph which corresponds to a schedule
of makespan at most
j
k
OPT
− 1 ǫ + 1 ≤ OPT − ǫ + 1 ≤ OPT + (1 − ǫ)OPT = (2 − ǫ)OPT.
ǫ
Proof of Theorem 1.2. Run the algorithm in Theorem 1.1 with a parameter ζ ′ on the input instance
to obtain a schedule with makespan at most (1 + R(ǫ, ζ ′ ))OPT. Run the algorithm in Theorem 3.31
to get a (2 − ǫ)OPT makespan schedule. The better of the two schedules has an approximation
guarantee that is no worse than


√

1
′
min 1 +
ǫ + 3 − 2ǫ + ζ , 2 − ǫ .
2
31

Figure 6: The previous proﬁle of the approximation guarantee as a function of 1 ≤ τ ∗ ≤ 3 and
0 < ǫ ≤ 3/4. The two surfaces making up the proﬁle correspond to the guarantees 2 − ǫ from
Theorem 3.31 and 1 + 1/τ ∗ from the algorithm of Lenstra, Shmoys and Tardos [LST90]. The work
of Chakrabarty, Khanna and Li [CKL15] provided a 2 − ǫ0 guarantee for some positive ǫ0 > 0, which
is indicated as a red dot at the apex of the proﬁle.
Suppose that 2 − ǫ ≥ 17/9 + ζ. Then, ǫ ≤ 1/9 − ζ. So,
√
√


1
1
ǫ + 3 − 2ǫ + ζ ′ ≤ 1 +
ǫ + 3 − 2ǫ
1+
2
2

1
+ζ =1+ ·
2
ǫ=1/9
′



1 5
+
9 3



+ ζ′ =

17
+ ζ,
9

for ζ ′ = ζ.

4

Conclusion

In this paper we presented a purely ﬂow based local search algorithm for the (1, ǫ)-case of restricted assignment makespan minimization. The guarantees achieved by our algorithm improve signiﬁcantly over the previous best one due to Chakrabarty et al. [CKL15]. For an illustration
of the approximation proﬁle for the problem, see Figures 6 and 7.
We remark that the ideas presented in this paper do not crucially depend on the fact that
the instances contain exactly two diﬀerent job sizes. Nevertheless, we have chosen to present our
results in the (1, ǫ)-case as there are still certain obstructions which prevent us from achieving 2 − ǫ0
guarantees for the restricted case in general. A second reason is that the algorithm for the case
with two diﬀerent job sizes admits a clean description in terms of maximum ﬂows, as we have seen
earlier in Section 3.2.

32

Figure 7: Now, following Theorem 1.2, the worst case guarantee is greatest (roughly 1.89) for
instances with τ ∗ = 1 and ǫ ≈ 1/9 as shown in the ﬁgure. The third surface arises from the
guarantee of 1 + R(ǫ, ζ)/τ ∗ for 1 ≤ τ ∗ < 2 from the proof of Theorem 1.1.

References
[AFS12]

Arash Asadpour, Uriel Feige, and Amin Saberi. Santa claus meets hypergraph matchings.
ACM Transactions on Algorithms (TALG), 8(3):24, 2012. 2

[AKS15]

Chidambaram Annamalai, Christos Kalaitzis, and Ola Svensson. Combinatorial algorithm for restricted max-min fair allocation. In Proceedings of the Twenty-Sixth Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA,
January 4-6, 2015, pages 1357–1372, 2015. 2

[BS06]

Nikhil Bansal and Maxim Sviridenko. The santa claus problem. In Proceedings of the
thirty-eighth annual ACM symposium on Theory of computing, pages 31–40. ACM, 2006.
2, 6

[CKL15]

Deeparnab Chakrabarty, Sanjeev Khanna, and Shi Li. On (1, ε)-restricted assignment
makespan minimization. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1087–1101. SIAM, 2015. 1, 3, 32

[CLRS09] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliﬀord Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009. 12
[EKS08]

Tomáš Ebenlendr, Marek Křćal, and Jiří Sgall. Graph balancing: a special case of
scheduling unrelated parallel machines. In Proceedings of the nineteenth annual ACMSIAM symposium on Discrete algorithms, pages 483–490. Society for Industrial and Applied Mathematics, 2008. 3
33

[Fei08]

Uriel Feige. On allocations that maximize fairness. In Proceedings of the nineteenth
annual ACM-SIAM symposium on Discrete algorithms, pages 287–293. Society for Industrial and Applied Mathematics, 2008. 2

[HSS11]

Bernhard Haeupler, Barna Saha, and Aravind Srinivasan. New constructive aspects of
the lovasz local lemma. Journal of the ACM (JACM), 58(6):28, 2011. 2

[JR16]

Klaus Jansen and Lars Rohwedder. On the conﬁguration-lp of the restricted assignment
problem. arXiv preprint arXiv:1611.01934, 2016. 3

[LST87]

Jan Karel Lenstra, David B Shmoys, and Eva Tardos. Approximation algorithms for
scheduling unrelated parallel machines. In Foundations of Computer Science, 1987.,
28th Annual Symposium on, pages 217–224. IEEE, 1987. 1, 2

[LST90]

Jan Karel Lenstra, David B Shmoys, and Éva Tardos. Approximation algorithms for
scheduling unrelated parallel machines. Mathematical programming, 46(1-3):259–271,
1990. 2, 3, 30, 31, 32

[PS12]

Lukas Polacek and Ola Svensson. Quasi-polynomial local search for restricted max-min
fair allocation. In Automata, Languages, and Programming, pages 726–737. Springer,
2012. 2

[Sve12]

Ola Svensson. Santa claus schedules jobs on unrelated machines. SIAM Journal on
Computing, 41(5):1318–1341, 2012. 2

[WS11]

David P Williamson and David B Shmoys. The design of approximation algorithms.
Cambridge University Press, 2011. 2

A

Appendix

Proof of Lemma 3.3. Consider the bipartite graph G = (M ∪ Jb , E) where there is an edge {i, j} ∈
E if and only if i ∈ Γ(j). A perfect matching in G of size |Jb | corresponds to such a map. If there
is no such perfect matching, by Hall’s condition, there is a set S ⊆ Jb such that |NG (S)| < |S|.
Consider the following setting (y ∗ , z ∗ ) of variables in the dual of CLP (τ ∗ ).
(
(
1, if i ∈ S,
1, if i ∈ NG (S),
∗
∗
and zj =
yi =
0, else.
0, else.
It is now easily veriﬁed that (y ∗ , z ∗ ) is a feasible solution to the dual of CLP (τ ∗ ) deﬁned in (2.2).
We use here the fact that conﬁgurations C ∈ C(τ ∗ , i) for any
P machine
Pi ∈ M∗ contain at most
∗
∗
one big job since τ < 2. As the objective function value j∈J zj − i∈M yi attained by this
feasible solution (y ∗ , z ∗ ) is strictly positive, it follows that the dual of CLP (τ ∗ ) is unbounded–for
any λ > 0, (λy ∗ , λz ∗ ) is a feasible dual solution as well. Therefore, by weak duality, CLP (τ ∗ ) must
be infeasible, a contradiction.
Proof of Proposition 3.7. By ﬂow decomposition, the maximum ﬂow in Hσb (S, T ) has ﬂow paths
p1 , . . . , p|Hσb (S,T )| , each of which sends one unit of ﬂow from some vertex in S to some vertex in T .
The ﬂow paths may not share a vertex in T as sinks have unit vertex capacities in Hσb (S, T ) as
34

deﬁned in Deﬁnition 3.6. Each machine i ∈ M has at most one outgoing edge with unit capacity
in Gbσ due to Deﬁnition 3.1(c) and Deﬁnition 3.4. So the ﬂow paths may also not intersect in some
vertex in M \ T since there is at most one outgoing arc with unit capacity. Similarly, they may not
share a vertex in Jb as there is only one incoming arc of unit capacity to a vertex in Jb in Gbσ using
Deﬁnition 3.1 and Deﬁnition 3.4 .
Claim A.1. ∀1 ≤ τ ∗ < 2, 0 < ǫ < 1, ζ > 0,


(2R − δ − ǫ − 1 − τ ∗ µ1 µ2 − (1 + 2τ ∗ + R)µ1 ) · (δ(1 − µ2 ) − 2µ2 ) − (1 − µ2 )(1 − R) − µ2 τ ∗ > 0,

where µ1 = min{1, ζ}/4, µ2 = min{δ, ζ}/4, δ =

√



√
3 − 2ǫ − 1 /2, and R = ǫ + 3 − 2ǫ /2 + ζ.

Proof. The statement is true if it is true for τ ∗ = 2. To prove that the bracketed expression is
positive we substitute the values of µ1 , µ2 , δ and R from (3.1) and the statement of Theorem 1.1,
and additionally set τ ∗ = 2 to get the statement





√

 1

1 √
1 √
1
min
2ζ + ǫ + 3 − 2ǫ − 2
3 − 2ǫ − 1 , ζ −
3 − 2ǫ − 1 , ζ − 1
2
2
4
2




√


1 1 √
1 √
3 − 2ǫ + 3 min
3 − 2ǫ − 1 , ζ − 3 − 2ǫ + 1 ×
+
16 4
2






√
√


1 √
3 − 2ǫ − 1 , ζ + 2ζ + ǫ + 3 − 2ǫ + 10 − 4 4ζ + 3 − 2ǫ − 1 > 0.
min{1, ζ} min
2
1
− min
2



Using a standard computer algebra system for eliminating quantiﬁers over reals, we can verify the
truth of the above statement for all 0 < ǫ < 1 and ζ > 0.
Claim A.2. ∀0 < ǫ < 1, ζ > 0,
where µ2 = min{δ, ζ}/4, and δ =

√

δ(1 − µ2 ) − 2µ2 > 0,

3 − 2ǫ − 1 /2.

Proof. Substituting the values of µ2 and δ, the statement reads


√
√



1 √
4 3 − 2ǫ − 1 >
3 − 2ǫ + 3 min
3 − 2ǫ − 1 , ζ .
2

It suﬃces to verify that statement
√ assuming that the min term always evaluates to the ﬁrst argument,
which then reduces
to ǫ + 3 3 − 2ǫ > 4. Let f (ǫ) denote the expression on the left. Then,
√
f ′ (ǫ) = 1 − 3/( 3 − 2ǫ) is negative over the range [0, 1], f (0) − 4 > 0 and f (1) − 4 = 0.

35

