Closing the Gap for Makespan Scheduling
via Sparsification Techniques∗
Klaus Jansen1 , Kim-Manuel Klein1 , and José Verschae2

arXiv:1604.07153v1 [] 25 Apr 2016

1

University of Kiel, Department of Computer Science, Kiel, Germany.
E-mail:{kj,kmk}@informatik.uni-kiel.de
2
Pontificia Universidad Católica de Chile, Facultad de Matemáticas & Escuela
de Ingenierı́a, Santiago, Chile. E-mail:jverschae@uc.cl
April 26, 2016

Abstract
Makespan scheduling on identical machines is one of the most basic and fundamental
packing problems studied in the discrete optimization literature. It asks for an assignment of
n jobs to a set of m identical machines that minimizes the makespan. The problem is strongly
NP-hard, and thus we do not expect a (1 + ε)-approximation algorithm with a running
time that depends polynomially on 1/ε. Furthermore, Chen et al. [3] recently showed that
1−δ
a running time of 2(1/ε)
+ poly(n) for any δ > 0 would imply that the Exponential
Time Hypothesis (ETH) fails. A long sequence of algorithms have been developed that
try to obtain low dependencies on 1/ε, the better of which achieves a running time of
2
2Õ(1/ε ) + O(n log n) [11]. In this paper we obtain an algorithm with a running time of
2Õ(1/ε) + O(n log n), which is tight under ETH up to logarithmic factors on the exponent.
Our main technical contribution is a new structural result on the configuration-IP. More
precisely, we show the existence of a highly symmetric and sparse optimal solution, in which
all but a constant number of machines are assigned a configuration with small support. This
structure can then be exploited by integer programming techniques and enumeration. We
believe that our structural result is of independent interest and should find applications to
other settings. In particular, we show how the structure can be applied to the minimum
makespan problem on related machines and to a larger class of objective functions on parallel
machines. For all these cases we obtain an efficient PTAS with running time 2Õ(1/ε) +
poly(n).

1

Introduction

Minimum makespan scheduling is one of the foundational problems in the literature on approximation algorithms [7, 8]. In the identical machine setting the problem asks for an assignment
of a set of n jobs J to a set of m identical machines M. Each job j ∈ J is characterized by
a non-negative processing time pj ∈ Z>0 . The load of a machine is the total processing time
of jobs assigned to it, and our objective is to minimize the makespan, that is, the maximum
machine load. This problem is usually denoted P ||Cmax . It is well known to admit a polynomial time approximation scheme (PTAS) [10], and there has been many subsequent works
improving the running time or deriving PTAS’s for more general settings. The fastest PTAS for
2
3
P ||Cmax achieves a running time of 2O(1/ε ) log (1/ε)) + O(n log n) for (1 + ε)-approximate solutions [11]. Very recently, Chen et al. [3] showed that, assuming the exponential time hypothesis
∗ This work was partially supported by DFG Project, Entwicklung und Analyse von effizienten polynomiellen
Approximationsschemata für Scheduling- und verwandte Optimierungsprobleme, Ja 612/14-2, by FONDECYT
project 3130407, and by Nucleo Milenio Información y Coordinación en Redes ICM/FIC RC130003.

1

(ETH), there is no PTAS that yields (1 + ε)-approximate solutions for ε > 0 with running time
1−δ
2(1/ε)
+ poly(n) for any δ > 0 [3].
Given a guess T ∈ N on the optimal makespan, which can be found with binary search, the
problem reduces to deciding the existence of a packing of the jobs to m machines (or bins) of
capacity T . If we aim for a (1 + ε)-approximate solution, for some ε > 0, we can assume that
all processing times are integral and T is a constant number, namely T ∈ O(1/ε2 ). This can
be achieved with well known rounding and scaling techniques [1, 2, 9] which will be specified
later. Let π1 < π2 < . . . < πd be the job sizes appearing in the instance after rounding, and
let bk denote the number of jobs of size πk . The mentioned rounding procedure implies that
the number of different job sizes is d = O((1/ε) log(1/ε)). Hence, for large n we obtain a highly
symmetric problem where several jobs will have the same processing time. Consider the knapsack
polytope P = {c ∈ Rd≥0 : π · c ≤ T }. A packing on one machine can be expressed as a vector
c ∈ Q = Zd ∩ P, where ck denotes the number of jobs of size πk assigned to the machine.
Elements in Q = Zd ∩ P are called configurations. Considering a variable xc ∈ Z≥0 that decides
the multiplicity of configuration c in the solution, our problem reduces to solving the following
linear integer program (ILP):
[conf-IP]

X

c · xc = b,

(1)

xc = m,

(2)

c∈Q

X

c∈Q

xc ∈ Z≥0

for all c ∈ Q.

(3)

In this article we derive new insights on this ILP that help us to design faster algorithms
for P ||Cmax and other more general problems. These including makespan scheduling on related
machines Q||Cmax , and a more general class of objective functions on parallel machines. We
4
show that all these problems admit a PTAS with running time 2O((1/ε) log (1/ε)) +poly(n). Hence,
our algorithm is best possible up to polylogarithmic factors in the exponent assuming ETH [3].

1.1

Literature Review

There is an old chain of approximation algorithms for P ||Cmax , starting from the seminal work
by Graham [7, 8]. The first PTAS was given by Hochbaum and Shmoys [10] and had a running
2
2
2
time of (n/ε)O((1/ε) ) = nO((1/ε) log(1/ε)) . This was improved to nO((1/ε) log (1/ε)) by Leung [16].
Subsequent articles improve further the running time. In particular Hochbaum and Shmoys
poly(1/ε)
(see [9]) and Alon et al. [1,2] obtain an efficient PTAS 1 (EPTAS) with running time 2(1/ε)
+
O(n log n). Alon et al. [1,2] consider general techniques that work for several objective functions,
including all Lp -norm of the loads and maximizing the minimum machine load.
2
3
The fastest PTAS known up to date for P ||Cmax achieves a running time of 2O((1/ε) log (1/ε)) +
O(n log n) [11]. More generally, this work gives an EPTAS for the case of related (uniform)
machines, where each machine i ∈ M has a speed si and assigning to i job j implies a processing
2
3
time of pj /si . For this more general case the running time is 2O((1/ε) log (1/ε)) + poly(n). For the
simpler case of P ||Cmax , the ILP can be solved directly since the number of variables is a constant.
This can be done with Lentras’ algorithm [15], or even with Kannan’s algorithm [14] that gives an
improved running time. This technique yields a running time that is doubly exponential in 1/ε.
This was, in essence, the approach by Alon et al. [1, 2] and Hochbaum and Shmoys [9]. To lower
the dependency on 1/ε, Jansen [11] uses a result by Eisenbrand and Shmonin [4] that implies
the existence of a solution x with support of size at most O(d log(dT )) = O((1/ε) log2 (1/ε)).
First guessing the support and then solving the ILP with O((1/ε) log2 (1/ε)) integer variables
2
3
and using Kannan’s algorithm yields the desired running time of 2O((1/ε) log (1/ε)) + O(n log n).
1 That is, a PTAS whose running time is f (1/ε)poly(|I|) where |I| is the encoding size of the input and f is
some function.

2

The configuration ILP has recently been studied in the context of the (1-dimensional) cutting
stock problem. In this case, the dimension d is constant, T = 1, and π is a rational vector.
Moreover, π and b are part of the input. Goemans and Rothvoß [5] obtain an optimal solution
O(d)
in time log(∆)2
, where ∆ is the largest number appearing in the denominator of πk or the
multiplicities bk . This is achieved by first showing that there exists a pre-computable set Q̃ ⊆ Q
with polynomial many elements, such that there exists a solution x that gives all but constant
(depending only on d) amount of weight to Q̃. We remark that applying this result to a rounded
instance of P ||Cmax yields a running time that is doubly exponential on 1/ε.

1.2

Our Contributions

Our main contribution is a new insight on the structure of the solutions of [conf-IP]. These
properties are specially tailored to problems in which T is bounded by a constant, which in the
case of P ||Cmax can be guaranteed by rounding and scaling. The same holds for Q||Cmax with
a more complex rounding and case analysis.
We first classify configurations by their support. We say that a configuration is simple if its
support is of size at most log(T + 1), otherwise it is complex. Our main structural result2 states
that there exists a solution x in which all but O(d log(dT )) weight is given to simple configurations, the support is bounded by O(d log(dT )) (as implied by Eisenbrand and Shmonin [4]) and
no complex configuration has weight larger than 1.
Theorem 1 (Thin solutions). Assume that [conf-IP] is feasible. Then there exists a feasible
solution x to [conf-IP] such that:
1. if xc > 1 then the configuration c is simple,
2. the support of x satisfies | supp(x)| ≤ 4(d + 1) log(4(d + 1)T ), and
P
3.
c∈Qc xc ≤ 2(d + 1) log(4(d + 1)T ), where Qc denotes the set of complex configurations.

We call a solution satisfying the properties of the theorem thin. The theorem can be shown by
iteratively applying a sparsification lemma that shows that if a solution gives a weight of two or
more to a complex configuration, then we can replace this partial solution by two configurations
with smaller support. The sparsification lemma is shown by a simple application of the pigeonhole
principle. The theorem can be shown by mixing this technique with the theorem of Eisenbrand
and Shmonin [4] and a potential function argument.
As an application to our main structural theorem, we derive a PTAS for P ||Cmax by first
guessing the jobs assigned to complex configurations. An optimal solution for this subinstance
can be derived by a dynamic program. For the remaining instance we know the existence of a
solution using only simple configurations. Then we can guess the support of such solution and
solve the corresponding [conf-IP] restricted to the guessed variables. The main use of having
simple configurations is that we can guess the support of the solution much faster, as the number
of simple configuration is (asymptotically) smaller than the total number of configurations. The
4
complete procedure takes time 2O((1/ε) log (1/ε)) + O(n log n). Moreover, using the rounding and
case analysis of Jansen [11], we derive an mixed integer linear program that can be suitably
decomposed in order to apply our structural result iteratively. This yields a PTAS with a
4
running time of 2O((1/ε) log (1/ε)) + poly(n) for Q||Cmax .
Similarly, we can extend our results to derive PTAS’s for a larger family of objective functions
as considered by Alon et al. [1,2]. Let ℓi denote the load of machine i, that is, the total processing
time of jobs assigned to machine i for a given solution. Our techniques then gives a PTAS with
the same running time for the problem of minimizing the Lp -norms of the loads (for fixed p),
and maximizing mini∈M ℓi , among others. To solve this problem, we can round the instance and
2 We remark the resemblance of this structure to the result by Goemans and Rothvoß [5]. Indeed, similar to
their result, we can precompute a subset of configurations such that all but a constant amount of weight of the
solution is given to such set. In their case the set is of cardinality polynomial on the input and is constructed
by covering the integral solutions of the knapsack polytope by parallelepipeds. In our case, all but O(d log dT )
weight is given to simple configurations.

3

state an IP analogous to [conf-IP] but considering an objective function. However, the objective
function prevents us to use the main theorem as it is stated. To get over this issue, we study
several ILPs. In each ILP we consider xc to be a variable only if c has a given load, and fix
the rest to be some optimal solution. Applying to each such ILP Theorem 1, plus some extra
ideas, yields an analogous structural theorem. Afterwards, an algorithm similar to the one for
makespan minimization yields the desired PTAS.
From an structural point of view, our sparsification lemma has other consequences on the
structure of the knapsack polytope and the LP-relaxation of the [conf-IP]. More precisely, we
can show that any vertex of the convex hull of Q must be simple. This, for example, helps us
2
2
to upper bound the number of vertices by 2O(log (T )+log (d)) . Moreover, we can show that the
configuration-LP, obtained by replacing the integrality restriction in [conf-IP] by x ≥ 0, if it is
feasible then admits a solution whose support consist purely of simple configurations. Due to
space limitations we leave many details and proofs to the appendix.

2

Preliminaries

We will use the following notation throughout the paper. By default log(·) = log2 (·), unless
stated otherwise. Given two sets A, I, we will denote by AI the set of all vectors indexed by I
with entries in A, that is, AI = {(ai )i∈I : ai ∈ A for all i ∈ I}. Moreover, for A ⊆ R, we denote
the support of a vector a ∈ AI as supp(a) = {i ∈ I : ai 6= 0}.
We consider an arbitrary knapsack polytope P = {c ∈ Rd≥0 : π · c ≤ T } where π ∈ Zd>0
is a non-negative integral (row) vector and T is a positive integer. We assume without loss
of generality that each coordinate πk of π is upper bounded by T (otherwise ck = 0 for all
c ∈ Zd ∩ P). We focus on the set of integral vectors in P which we denote by Q = Zd ∩ P. We
call an element c ∈ Q a configuration. Given b ∈ Rd , consider the problem of decomposing b as
a conic integral combination of m configurations. That is, our aim is to find a feasible solution
to [conf-IP], defined above.
A crucial property of the [conf-IP] is that there is always a solution with a support of small cardinality. This follows from a Caratheodory-type bound obtained by Eisenbrand and Shmonin [4].
Since we will need the argument later, we state the result applied to our case and revise its (very
elegant) proof. We split the proof in two lemmas.
For a given subset A ⊆ Q, let us denote by xA the indicator vector of A, that is xA
c = 1 if
c ∈ A, and 0 otherwise. Let us also denote by M the (d + 1) × |Q| matrix that defines the system
of equalities (1) and (2).
Lemma 2 (Eisenbrand and Shmonin [4]). Let x ∈ ZQ
≥0 be a vector such that | supp(x)| >
2(d + 1) log(4(d + 1)T ). Then there exist two disjoint sets A, B with ∅ 6= A, B ⊆ supp(x) such
that M xA = M xB .
Proof. Let s := | supp(x)|. Each coordinate of M is smaller than T . Hence, for any A ⊆ supp(x),
each coordinate of M xA is no larger than |A| · T ≤ sT . Thus, M xA belongs to {0, . . . , sT }d+1,
and hence there are at most (sT + 1)d+1 = 2(d+1) log(sT +1) different possibilities for vector M xA ,
over all possible subsets A ⊆ supp(x). On the other hand, there are 2s many different subsets
of supp(x).
We claim that s > (d + 1) log(sT + 1). Indeed, since s > 2(d + 1) log(4(d + 1)T ) then
s
T < 2 2(d+1) /(4(d + 1)). Hence,

4

!
s
s2 2(d+1)
+1
(d + 1) log(sT + 1) < (d + 1) log
4(d + 1)



s
s
≤ (d + 1) log 2 2(d+1)
+1
4(d + 1)



s
s
+ log
+1
= (d + 1)
2(d + 1)
4(d + 1)
s
s
≤ +
< s,
2 4 ln(2)
where the penultimate inequality follows since log(x) ≤ (x − 1)/ ln(2) for all x ≥ 1.
We obtain that 2s > 2(d+1) log(sT +1) . Hence, by the pigeonhole principle there are two
′
′
distinct subsets A′ , B ′ ⊆ supp(x) such that M xA = M xB . We can now define A = A′ \ B ′
and B = B ′ \ A′ and obtain M xA = M xB . It remains to show that A, B 6= ∅. Notice that if
′
′
A = ∅ then A′ ⊆ B ′ , and the last equality of M xA = M xB implies that |A′ | = |B ′ |. This
is a contradiction since then A′ = B ′ . We conclude that A 6= ∅. The proof that B 6= ∅ is
analogous.
Lemma 3 (Eisenbrand and Shmonin [4]). If [conf-IP] is feasible, then there exists a feasible
solution x such that | supp(x)| ≤ 2(d + 1) log(4(d + 1)T ).
Proof. Let x be a solution to [conf-IP] that minimizes | supp(x)| = s. Assume by contradiction
that s > 2(d + 1) log(4(d + 1)T ). We show that we can find another solution x′ to [conf-IP] with
| supp(x′ )| < | supp(x)|, contradicting the minimality of | supp(x)|. By Lemma 2, there exist two
disjoint subsets A, B ∈ supp(x) such that M xA = M xB . Moreover, let λ = min{xc : c ∈ A}.
Vector x′ := x − λxA + λxB is also a solution to [conf-IP] and has a strictly smaller support
since a configuration c∗ ∈ arg min{xc : c ∈ A} satisfies x′c∗ = 0.

3

Structural Results

Recall that we call a configuration c simple if | supp(c)| ≤ log(T + 1) and complex otherwise. An
important observation to show Theorem 1 is that if c is a complex configuration, then 2c can
be written as the sum of two configurations of smaller support. This is shown by the following
Sparsification Lemma.
Lemma 4 (Sparsification Lemma). Let c ∈ Q be a complex configuration. Then there exist two
configurations c1 , c2 ∈ Q such that
1. π · c1 = π · c2 = π · c,
2. 2c = c1 + c2 ,
3. supp(c1 ) ( supp(c) and supp(c2 ) ( supp(c).
Proof. Consider for each subset S ⊆ supp(c), a configuration cS ∈ Q such that cSi = ci if i ∈ S
and cS = 0 otherwise. As the number of subsets of supp(c) is 2| supp(c)| , and cR 6= cS if and only
if R 6= S, the collection of vectors V := {cS : S ⊆ supp(c)} has cardinality |V | = 2| supp(c)| .
On the other hand, for any vector cS ∈ V it holds that π · cS ≤ π · c ≤ T . Hence, π · cS ∈
{0, 1 . . . , T } can take only T + 1 different values. Using that c is a complex configuration and
hence 2| supp(c)| > 2log(T +1) = T + 1, the pigeonhole principle ensures that there are two different
non-empty configurations cS , cR ⊆ V with π · cS = π · cR . By removing the intersection, we can
assume w.l.o.g. that S and R have no intersection. We define c1 = c−cS +cR and c2 = c−cR +cS ,
which satisfy the properties of the lemma as
π · c1 = π · c − π · cS + π · cR = π · c
S

R

R

and

S

2c = c − c + c + c − c + c = c1 + c2 .
Since supp(c1 ) ⊆ supp(c) \ S and supp(c2 ) ⊆ supp(c) \ R, property 3 is satisfied.
5

With Lemma 4 we are ready to show Theorem 1. For the proof it is tempting to apply the
lemma iteratively, replacing any complex configuration that is used twice by two configurations
with smaller support. This can be repeated until there is no complex configuration taken multiple
times. Then we can apply the technique of Lemma 3 to the obtained solution to bound the
cardinality of the support. However, the last step might break the structure obtained if the
solution implied by Lemma 3 uses a complex configuration more than once. In order to avoid
this issue we consider a potential function. We show that a vector minimizing the chosen potential
uses each complex configuration at most once, and that the number of complex configurations in
the support is bounded. Finally, we apply the techniques from Lemma 3 restricted to variables
corresponding to simple configurations.
Proof of Theorem 1. Consider the following potential function of a solution x ∈ ZQ
≥0 of [conf-IP],
Φ(x) =

X

xc | supp(c)|.

complex config. c

Let x be a solution of [conf-IP] with minimum potential Φ(x), which is well defined since the set
of feasible solutions has finite cardinality. We show two properties of x.
P1: xc ≤ 1 for each complex configuration c ∈ Q.
Assume otherwise. Consider the two configurations c1 and c2 implied by the previous lemma.
We define a new solution x′e = xe for e 6∈ {c, c1 , c2 }, x′c1 = xc1 + 1, x′c2 = xc2 + 1 and x′c = xc − 2.
Since | supp(c1 )| < | supp(c)| and | supp(c2 )| < | supp(c)|, we obtain that Φ(x′ ) < Φ(x) which
contradicts the minimality of Φ(x).
P2: The number of complex configurations in supp(x) is at most 2(d + 1) log(4(d + 1)T ).
Let x̃ be the vector defined as x̃c = xc if c ∈ Q is complex, and x̃ = 0 if c ∈ Q is simple.
Then Lemma 2 implies that there are exist two disjoint subsets A, B ⊆ supp(x̃) of complex
configurations such that M xA = M xB . Thus, the solution x′ = x − xA + xB and the solution
x′′ = x − xB + xA are feasible for [config-IP]. By linearity, the potential function on the new
solutions are Φ(x′ ) = Φ(x) − Φ(xA ) + Φ(xB ) or respectively Φ(x′′ ) = Φ(x) − Φ(xB ) + Φ(xA ).
If Φ(xA ) > Φ(xB ) or Φ(xB ) > Φ(xA ) then we have constructed a new solution with smaller
potential, contradicting our assumption on the minimality of Φ(x). We conclude that Φ(xB ) =
Φ(xA ) and thus Φ(x) = Φ(x′ ). By construction of x′ , we obtain that x′c > xc ≥ 1 for any complex
configuration c ∈ B. Having multiplicity ≥ 2 for a complex configuration c, we can proceed as
in Case 1 to find a new solution with decreased potential, which yields a contradiction.
Given these two properties, to conclude the theorem it suffices to upper bound the number
of simple configurations by 2(d + 1) log(4(d + 1)T ). Suppose this property is violated, then we
find two sets A, B ⊆ supp(x) of simple configurations (see Lemma 2) with M xA = M xB and
proceed as in Lemma 3. Since Lemma 3 is only applied to simple configurations, properties P1
and P2 continue to hold and the theorem follows.
Our techniques, in particular our Sparsification Lemma, imply two corollaries on the structure
of the knapsack polytope and the LP-relaxation implied by the [conf-IP].
Corollary 5. Every vertex of conv.hull(Q) is a simple configuration. Moreover, the total number
2
2
of simple configurations in Q is upper bounded by 2O(log (T )+log (d)) and thus the same expression
upper bounds the number of vertices of conv.hull(Q).
Proof. Consider a complex configuration c ∈ Q. By Lemma 4 we know that there exist c1 , c2 ∈ Q
with c1 , c2 6= c such that 2c = c1 + c2 . Hence, c is not a vertex of Q as it can be written as a
convex combination c = c1 /2 + c2 /2.
To bound the number of simple configurations fix a set D ⊆ {1, . . . , d}. Notice that the
number of configurations c with supp(c) = D is at most T |D|. For simple configurations it suffices
to take D with cardinality at most log(T + 1). Since the number of subsets D ⊆ {1, . . . , d} with

6

cardinality i is

d
i


, we obtain that the number of simple configurations is at most

⌊log(T +1)⌋ 

X
i=0


d
× (T + 1)log(T +1) ≤ (log(T + 1) + 1)dlog(T +1) × (T + 1)log(T +1)
i
2

= 2log(log(T +1)+1)+log(d) log(T +1) × 2log(T +1) log(T +1) = 2O(log

(d)+log2 (T ))

.

The following corollary follows as each complex configuration can be represented by a convex
combination of simple configurations.
Corollary 6. Let [conf-LP] be the LP relaxation of [conf-IP], obtained by changing each constraint xc ∈ Z≥0 to xc ≥ 0 for all c ∈ Q. If the LP is feasible then there exists a solution x such
that each configuration c ∈ supp(x) is simple.
Proof. Consider a solution x of [conf-LP]. Assume that there exists c ∈ Q such that c is
Pcomplex
and xcP
> 0. Then by the previous corollary, configuration c can be written as c = q∈Q λq q,
where q∈Q λq = 1, λq ≥ 0 for all q ∈ Q, and λq = 0 if q ∈ Q is complex. Consider a new
solution x′ defined as
(
0
if q = c,
′
xq =
xq + λq · xc if q 6= c.
This new solution is also feasible for [conf-LP]. As x′c = 0, the number of complex configurations in the support of the solution is reduced by 1. This procedure can be repeated until we
have a solution x̂ whose support contains only simple configurations.

4

Applications to Scheduling on Parallel Machines

In what follows we show how to exploit the structural insights of the previous section to derive
faster algorithms for parallel machines scheduling problems. We start by considering P ||Cmax ,
where we seek to assign a set of jobs J with processing times pj ∈ Z>0 to a set
P M of m machines.
For a given assignment a : J 7→ M, we define the load of a machine i as j:a(j)=i pj and the
makespan as the maximum load of jobs over all machines, which is the minimum time needed to
complete the execution of all jobs on the processors. The goal is to find an assignment J 7→ M
that minimizes the makespan.
We first follow well known rounding techniques [1, 2, 9, 10]. Consider an error tolerance
0 < ε < 1/3 such that 1/ε2 is an integer. To get an estimation of the optimal makespan, we
follow the standard dual approximation approach. First, we can use, e.g., the 2-approximation
algorithm by Graham [7] to get an initial guess of the optimal makespan. Using binary search,
we can then estimate the optimal makespan within a factor of (1 + ε) in O(log(1/ε)) iterations.
Therefore, it remains to give an algorithm that decides for a given makespan T , if there exists an
assignment with makespan (1+O(ε))T or reports that there exists no assignment with makespan
≤ T.
For a given makespan T we define the set of big jobs Jbig = {j ∈ J : pj ≥ εT } and the
set of small jobs Jsmall = J \ Jbig . The following lemma shows that small jobs can be replaced
from the instance by adding big jobs, each of size εT , as placeholders. Let S be the sum of
processing times of jobs in Jsmall and let S ∗ denote the next value of S rounded up to the next
multiple of εT , that is, S ∗ = εT · ⌈S/(εT )⌉. We define a new instance containing only big jobs
by J ∗ = Jbig ∪ Jnew , where Jnew contains S ∗ /(εT ) ∈ N jobs of size εT .
Lemma 7. Given a feasible assignment a : J 7→ M of jobs with makespan T . Then there exists
a feasible assignment aB : J ∗ 7→ M of makespan T ∗ ≤ (1 + ε)T . Similarly, an assignment
of jobs in J ∗ of makespan T ∗ can be transformed to an assignment of J of makespan at most
(1 + ε)T ∗ .
Proof. We modify the assignment a of jobs in J by replacing the set of small jobs on each
machine by jobs in Jnew . Let Si be the total processing time of small jobs assigned to machine i.
Then the small jobs are replaced by (at most) Si∗ /(εT ) jobs in Jnew , where Si∗ denotes the
7

P Si
P Si∗
S∗
value of Si rounded up to the next multiple of εT . As
εT ≥ ⌊
εT ⌋ = εT , the new solution
processes all jobs in Jnew and the load on each machine increases hence by at most εT . Having
an assignment for the big jobs J ∗ , we can easily obtain a schedule for jobs J , by adding the
small items greedily into the space of the placeholder jobs Jnew .
By scaling the processing times of jobs in J ∗ , we can assume that the makespan T has
value 1/ε2 . Also notice that we can assume that pj ≤ T for all j, otherwise we cannot pack all jobs
within makespan T . This implies that each job j ∈ J ∗ has a processing time of 1/ε ≤ pj ≤ 1/ε2 .
In the following we give a transformation of big jobs in J ∗ by rounding their processing times.
We first round the jobs to the next power of 1 + ε as p′j = (1 + ε)⌈log(1+ε) pj ⌉ , and thus all rounded
processing times belong to Π′ = {(1 + ε)k : 1/ε ≤ (1 + ε)k ≤ (1 + ε)/ε2 and k ∈ N}. We further
round processing times p′j to the next integer p̄j = ⌈p′j ⌉ and define a new set Π = {⌈p⌉ : p ∈ Π′ }.
Notice that Π only contains integers and |Π| ≤ |Π′ | ∈ O((1/ε) log(1/ε)).
Lemma 8. If there is a feasible schedule of jobs J ∗ with processing times pj onto m machines
with makespan T ∗ ≤ (1 + ε)T , then there is also a feasible schedule of jobs J ∗ with rounded
processing p̄j with a makespan of at most (1 + 5ε)T . Furthermore, the number of different
processing times is at most |Π| ∈ O((1/ε) log(1/ε)).
Proof. Consider a feasible schedule of jobs in J ∗ with processing times pj onto m machines
with makespan T ∗ . LetPJi1 , . . . , JirPbe the set of jobs processed on machine i i.e. a(Jik ) = i
for k = 1, . . . , r. Then rj=1 p′j ≤ rj=1 (1 + ε)pj ≤ (1 + ε)T ∗ . Hence, the same assignment a
with processing times p′j yields a makespan of at most (1 + ε)T ∗ ≤ (1 + ε)2 T = 1/ε2 + 2/ε + 1.
Since p′j ≥ pj ≥ 1/ε, on every machine are at most 1/ε + 2 jobs. Hence, rounding the processing
times p′j of each job to the next integer increase the load on each machine by at most 1/ε + 2.
Recalling that ε < 1/3, we obtain a feasible schedule with makespan at most (1+ε)T ∗ +1/ε+2 ≤
1/ε2 + 3/ε + 3 < T + 5εT .
In what follows we give an algorithm that decides in polynomial time the existence of a
solution for instance J ∗ with processing times p̄j and makespan T̄ = ⌊(1 + 5ε)T ⌋. We call
numbers in Π by π1 , . . . , πd and define the vector π = (π1 , π2 , . . . , πd ) ∈ Nd of rounded processing
times. We consider configurations to be vectors in Q = P ∩ Zd , where P = {c ∈ Rd≥0 : π · c ≤ T̄ }
is a knapsack polytope (see Section 3). As before, we say that a configuration is simple if
| supp(c)| ≤ log(T̄ + 1), and complex otherwise. For a given assignment of jobs to machines, we
say that a machine follows a configuration c if ck is the number of jobs of size πk assigned to
the machine. We denote by Qc ⊆ Q the set of complex configurations and by Qs ⊆ Q the set of
simple configurations.
Let bk be the number of jobs of size πk in the instance J ∗ (with processing times p̄). Consider
an ILP with integer variables xc for each c ∈ Q, which denote the number of machines that
follow configuration c. With these parameters the problem of scheduling all jobs in a solution of
makespan T̄ is equivalent to finding a solution to [conf-IP]. To solve the ILP we use, among other
techniques, Kannan’s algorithm [14] which is an improvement on the algorithm by Lenstra [15].
The algorithm has a running time of 2O(N log N ) s where N is the number of variables and s is
number of bits used to encode the input of the ILP in binary.
By Theorem 1, if [conf-IP] is feasible then there exists a thin solution. In particular if one
configuration c is used by more than one machine then c is simple, and the total number of used
configurations is 4(d + 1) log(4(d + 1)T̄ ) ∈ O((1/ε) log2 (1/ε)). Additionally, the number of machines following a complex configurations is at most 2(d + 1) log(4(d + 1)T̄ ) ∈ O((1/ε) log2 (1/ε)).
We consider the following strategy to decide the existence of a schedule of makespan T̄ .
Algorithm 9.
1. For each processing time πk , guess the number bck ≤ bk of jobs covered by complex configurations.
2. Find a minimum number of machines mc to schedule jobs bc with makespan T̄ .

8

3. Guess the support of simple configurations Q̄s ⊆ Qs used by a thin solution, with |Q̄s | ≤
4(d + 1) log(4(d + 1)T̄ ) ∈ O((1/ε) log2 (1/ε)).
4. Solve the ILP restricted to configurations in Q̄s :
X
c · xc = b − bc ,
c∈Q̄s

X

xc = m − mc ,

c∈Q̄s

xc ∈ Z≥0

for all c ∈ Q̄s .

One of the key observations to prove the running time of the algorithm is that the number
of simple configurations |Qs | is bounded by a quasi polynomial term:
2

|Qs | ≤ 2O(log

(1/ε))

.

This follows easily by Corollary 5, using that |T̄ | ∈ O(1/ε2 ) and d = |Π| ∈ O((1/ε) log(1/ε)).
Lemma 10. Algorithm 9 can be implemented with a running time of 2O((1/ε) log

4

(1/ε))

log(n).

Proof. In step 1, the algorithm guesses which jobs are processed on machines following a complex configurations. Since each configuration contains at most O(1/ε) jobs, there are at most
O(mc /ε) = O((1/ε2 ) log2 (1/ε)) jobs assigned to such machines. For each size πk ∈ Π, we guess
the number bck of jobs of size πk assigned to such machines. Hence, we can enumerate all possibil2
ities for jobs assigned to complex machines in time 2O((1/ε) log (1/ε)) . After guessing the jobs, we
can assign them to a minimum number of machines in step 2 (with makespan T̄ ) with a simple
dynamic program that stores vectors (ℓ, z1 , . . . , zd ) with zk ≤ bck being the number of jobs of
size πk used in the first ℓ ≤ mc processors [13]. The size of the dynamic programming table is
Q
O(mc dk=1 (bck +1)). For any vector (ℓ, z1 , . . . , zd ), determining whether it corresponds to a feasible solution can be done by checking all vectors of the type (ℓ−1, z1′ , . . . , zd′ ) for zk′ ≤ zk . Thus, the
Qd
running time of the dynamic program is O(mc [ k=1 (bck + 1)]2 ). Since bck ∈ O((1/ε2 ) log2 (1/ε))
for each k, recalling that mc ∈ O((1/ε) log2 (1/ε)), and that d = |Π| ∈ O((1/ε) log(1/ε)), we
2
obtain that step 2 can be implemented with 2O((1/ε) log (1/ε)) running time.
In step 3, our algorithm guesses the support of a thin solution x. Recall that if x is thin
then | supp(x)| ≤ 4(d + 1) log(4(d + 1)T̄ ) = O((1/ε) log2 (1/ε)). Let D = 4(d + 1) log(4(d + 1)T̄ ).
Then this guess can be done in time

D 
X
|Qs |
i=0

i

≤ (D + 1)|Qs |D ≤ 2O((1/ε) log

4

(1/ε))

.

We remark that for this step is that thin solutions are particularly useful. Indeed, guessing the
2
3
support on the original ILP takes time 2O((1/ε) log (1/ε)) .
In step 4, the number of variables of the restricted ILP is 4(d+1) log(4(d+1)T̄ ) = O((1/ε) log2 (1/ε)).
Moreover, the size of the input can be bounded by O((1/ε2 ) log3 (1/ε) log(n)). Running Kannan’s
3
algorithm [14] to solve the ILP takes time 2O((1/ε) log (1/ε)) log(n). Hence, the total running time
4
of our algorithm can be bounded by 2O((1/ε) log (1/ε)) log(n).
Putting all pieces together, we conclude with the following theorem.
Theorem 11. The minimum makespan problem on parallel machines P ||Cmax admits an EPTAS
4
with running time 2O((1/ε) log (1/ε)) + O(n log n).
Proof. Consider a scheduling instance with job set J , processing times pj for j ∈ J and machine set M. The greedy algorithm by Graham to obtain a 2-approximation can be implemented in O(n log n). After guessing the makespan T , the processing times are sorted and
rounded as described in Lemma 8. The rounding step can easily be implemented in O(n) time.
9

Applying Algorithm 9 after the rounding needs, according to Theorem 10, a running time of
4
2O((1/ε) log (1/ε)) log(n) time. Since there are at most O(log(1/ε)) many guessing rounds for the
4
makespan, we obtain a total running time of O(n log n + log(1/ε) · n) + 2O((1/ε) log (1/ε)) log(n).
4
4
1
1
1
1
If n ≤ 2 ε log ( ε ) then the running time is upper bounded by 2O( ε log ( ε )) , otherwise, the run4 1
1
ning time is at most O(n log n). In any case, the running time can be bounded by 2O( ε log ( ε )) +
O(n log n).

4.1

Extension to other objectives

We now consider a more general family of objective functions defined by Alon et al. [1, 2]. For a
fixed function f : R≥0 → R≥0 , we consider the following two objective functions:
P
(II) min maxi∈M f (ℓi ),
(I) min i∈M f (ℓi )
where ℓi denotes the load of machine i. Analogously, we study maximization versions of the
problems
P
(II’) max mini∈M f (ℓi ),
(I’) max i∈M f (ℓi )

For the minimization versions of the problem we assume that f is convex, while for (I’) and
(II’) we assume it is concave. Moreover, we will need that the function satisfies the following
sensitivity condition.
Condition 12. For all ε > 0 there exists δ = δ(ε) > 0 such that for all x, y ∈ R≥0 ,
(1 − δ)y ≤ x ≤ (1 + δ)y

⇒

(1 − ε)f (y) ≤ f (x) ≤ (1 + ε)f (y).

Alon et al. showed that each problem in that family admits a PTAS with running time
h(ε) + O(n log n), where h(ε) is a constant term that depends only on ε. Moreover, if δ(ε) in the
poly(1/ε)
condition further satisfies that 1/(δ(ε)) ∈ O(1/ε), the running time is 2(1/ε)
+ O(n log n).
In what follows we show how to improve this dependency. Since 1/(δ(ε)) ∈ O(1/ε), we know
that, for small enough ε, there exists a constant γ (independent of ε and δ) such that 1/δ ≤ γ/ε.
Moreover, we can assume w.l.o.g. that δ ≤ ε, and thus δ ≤ ε ≤ γδ.
It is worth noticing that many interesting functions belong to this family. In particular (II)
with f (x) = x corresponds to the minimum makespan problem, (I) with f (x) = xp , for constant
p, corresponds to a problem that is equivalent to minimizing the Lp -norm of the vector of loads.
Similarly, (II’) with f (x) = x corresponds to maximizing the minimum machine load. Notice
that for all those objectives we have that 1/δ = O(1/ε).
The techniques of Alon et al. [2] are based on a rounding method and then solving an ILP.
We based our results in the same rounding techniques. Consider an arbitrary instance of a
scheduling problem on identicalPmachines with objective function (I), (II), (I’) or (II’). Their
first observation is that, if L = j pj /m is the average machine load, then a job with pj ≥ L is
scheduled alone on a machine in an optimal solution [2]. Hence, we can remove such job and a
machine from the instance. In what follows, we assume without loss of generality, that pj < L
for all j. For the sake of brevity, we summarize the rounding techniques of Alon et al. in the
following theorem.
Theorem 13 (Alon et al. [2]). Consider an instance for the scheduling problem with job set J ,
identical machines M, and processing times pj for j ∈ J such that pj < L for all j. There
exists a linear time algorithm that creates a new instance I ′ with job set J ′ , machine set M,
and processing times p′j . Moreover, there is an integer λ ≥ 1/δ with λ ∈ O(1/δ) such that the
new instance satisfies the following:
1. Each job j in I ′ has processing time L/λ ≤ p′j ≤ L, and p′j is a integer multiple of L/λ2 .
P
2. If L′ = j p′j /m then L ≤ L′ ≤ (1 + 2/λ)L.

3. Let Opt and Opt′ be the optimal value of instances I and I ′ , respectively. Then (1 −
ε)Opt ≤ Opt′ ≤ (1 + ε)Opt.
10

4. There exists a linear time algorithm that transforms a feasible solution for instance I ′
with objective value V
to a feasible solution for I with objective value V ′ such that
(1 − ε)V ≤ V ′ ≤ (1 + ε)V .
Given this result, it suffices to find a (1 + ε)-approximate solution for instance I ′ .
To
do so, we further round the processing times as in the previous section by defining p̄j as the
′
value (1 + δ)⌈log1+δ pj ⌉ rounded up to the next multiple of L/λ2 for all j ∈ J ′ . Notice that
′
p̄j ≤ (1 + δ)⌈log1+δ pj ⌉ + L/λ2 ≤ (1 + δ)p′j + L/λ2 ≤ (1 + δ)p′j + p′j /λ ≤ (1 + 2δ)p′j ≤ (1 + δ)2 p′j .
Hence, for any assignment that gives a load ℓi on machine i for p′j , the same assignment has a
load ℓ̄i with ℓi ≤ ℓ̄i ≤ (1 + δ)2 ℓi . By Condition 12 we conclude that the new optimal value Opt
satisfies that (1 − O(ε))Opt ≤ Opt ≤ (1 + O(ε))Opt.
Let Π = {π1 , . . . , πd } be the distinct values that the processing times p̄j can take. Notice
that d = |Π| = O((1/δ) log(1/δ)). We consider the knapsack polytope with capacity T̄ := 4L,
that is P = {c ∈ Rd≥0 : π · c ≤ T̄ }. Notice that π and T̄ are integer multiples of L/λ2 , and thus
P = {c ∈ Rd≥0 : π/(L/λ2 ) · c ≤ T̄ /(L/λ2 )}. The following lemma, that is a simple adaptation
of an observation by Alon et al. [2], shows that there exists an optimal solution for the rounded
instance that uses only configurations in P.
Lemma 14. For ε > 0 small enough, the rounded instance with processing times p̄j admits an
optimal solution with makespan at most 4L.
P
Proof. Among all optimal solutions to the problem, consider one that minimizes i ℓ2i , where ℓi
is the load on machine i. Assume that there exists a machine i such that ℓi > 4L. Notice that
X
X
Theorem 13
≤
(1 + δ)2 (1 + 2/λ)L ≤ (1 + δ)4 L.
p′j /m = (1 + δ)2 L′
p̄j /m ≤ (1 + δ)2
j

j

P
Since δ ≤ ε, for ε small enough (ε ≤ 1/10 suffices) we have that (1+δ)4 ≤ 2 and thus j p̄j /m ≤
2L. Also, recall that p̄j ≤ (1+δ)2 p′j ≤ (1+δ)2 L ≤ P
2L for any j, where the second to last inequality
follows from Theorem 13. Since ℓmin = mini ℓi ≤ j p̄j /m ≤ 2L, then ℓi − ℓmin > 4L − 2L = 2L.
Then, for any job j, we have that pj < ℓi − ℓmin . Let j ∗ be any job assigned to machine i. Hence,
in particular we have that pj ∗ < ℓi − ℓmin.
Recall that for problems (I) and (II) function f is convex. Hence, it holds that f (x + ∆) +
f (y − ∆) ≤ f (x) + f (y) for all 0 ≤ x ≤ y with 0 ≤ ∆ ≤ y − x [2]. Moreover, the inequality
becomes strict if f is strictly convex. Setting x = ℓmin , y = ℓi and P
∆ = pj ∗ , the inequality implies
that moving job j ∗ to machine i∗ ∈ arg mini ℓi decreases strictly i ℓ2i . Moreover, the objective
function (I) does not increase when performing this move, which yields a contradiction for this
objective. Similarly, for problem (II) the objective does not increase since max{f (ξ) : ξ ∈ [x, y]}
is always attained at x or y for f convex. This yields a contradiction for (II).
Analogously, for problems (I’) and (II’) function f is concave and thus f (x + ∆) + f (y − ∆) ≥
f (x) + f (y) holds forPall 0 ≤ x ≤ y with 0 ≤ ∆ ≤ y − x [2]. Hence, moving job j ∗ to
machine i∗ decreases i ℓ2i but does not increase the objective (I’). Since f concave implies that
min{f (ξ) : ξ ∈ [x, y]} is always attained at x or y, we also obtain a contradiction for (II’). The
lemma follows.
P
Let L = j pj /m be the average machine load (of the original instance). After our rounding
we obtain an instance I ′ with job set J ′ and processing times p̄j for j ∈ J ′ . Moreover, the p̄j
are multiples of L/λ2 , where λ ≥ 1/δ is an integer such that λ = O(1/δ), and also p̄j ≥ L/λ. It
holds that there exists an optimal solution of the rounded instance with makespan at most 4L,
see Lemma 14 (in particular p̄j ≤ 4L for all j). Let Π = {π1 , . . . , πd } be the distinct values that
the processing times p̄j can take. Our rounding guarantees that d = |Π| = O((1/δ) log(1/δ)).
We consider the knapsack polytope with capacity T̄ := 4L, that is P = {c ∈ Rd≥0 : π · c ≤ T̄ }.
Notice that π and T̄ are integer multiples of L/λ2 , and that P can also be written as {c ∈ Rd≥0 :
π/(L/λ2 ) · c ≤ T̄ /(L/λ2 )}.
As before, we say that a configuration is simple if | supp(c)| ≤ log(T̄ + 1), and complex
otherwise. We denote by Qc ⊆ Q the set of complex configurations and by Qs ⊆ Q the set of
simple configurations. In what follows we focus on objective function (I).
11

We set an ILP for the problem as before. Notice that each configuration c incurs a cost of
fc := f (π · c). Moreover, we round and scale the values fc by defining f¯c = ⌈fc /(εfmin)⌉, where
fmin = minc∈Q fc . It is not hard to see that solving a problem with those coefficients yields a
(1 + ε)-approximate solution to the optimal solution of I ′ with processing times p̄j . Let also bk
′
be the number of jobs j of processing time
P p̄j = πk in J . Consider the ILP obtained by adding
to [conf-IP] the objective function min c∈Q f¯c · xc . We call this ILP [cost-conf-IP]. With our
previous discussion, it suffices to solve this ILP optimally. To solve this problem, we first notice
that the largest coefficient in the objective can be bounded as follows.
Lemma 15. If f satisfies Condition 12 then the largest value maxc∈Q f¯c is upper bounded by
1/δ O(1) .
Proof. We first bound (maxc∈Q fc )/(εfmin). Notice that Condition 12 implies that f is continuous on R≥0 , and thus it admits a minimum and maximum in the interval [L/λ, 4L]. Let
xmin ∈ arg min{f (x) : x ∈ [L/λ, 4L]} and xmax ∈ arg max{f (x) : x ∈ [L/λ, 4L]}.
Consider first the case in which xmin ≤ xmax (this is not always true since f might not be
monotone). We now use Condition 12 iteratively. Let y k := (1 + δ)k xmin . Since y k ≤ y k−1 (1 + δ),
Condition 12 implies that f (y k ) ≤ (1 + ε)f (y k−1 ). Iterating this idea we obtain that f (y k ) ≤
(1 + ε)k f (y 0 ). Taking k = ⌈log1+δ (xmax /xmin )⌉ implies that xmax ≤ y k ≤ xmax (1 + δ) and thus,
by Condition 12, it holds that f (y k ) ≥ (1 − ε)f (xmax ). Recall that δ ≤ ε ≤ γδ. We obtain that

f (xmax ) ≤

f (y k )
(1 + ε)k
≤
f (xmin )
1−ε
1−ε
(1 + ε)log1+δ (xmax /xmin )+1
≤
f (xmin )
1−ε
(1 + ε)log1+δ (4λ)+1
f (xmin )
≤
1−ε
1+ε
=
(4λ)log1+δ (1+ε) f (xmin )
1−ε
1+ε
(4λ)log1+δ (1+γδ) f (xmin )
≤
1−ε
= (1/δ)O(1) f (xmin ),

where the last expression follows since log1+δ (1 + γδ) = ln(1 + γδ)/ ln(1 + δ) ≤ γδ/ ln(1 + δ) =
O(γ) = O(1) (for δ small enough), and since λ = O(1/δ). We conclude that
max f¯c ≤ (f (xmax ))/(εf (xmin )) + 1 ≤ (1/ε)(1/δ)O(1) + 1 = (1/δ)O(1) .
c∈Q

For the case in which xmax ≤ xmin we define the sequence y k := (1 − δ)k xmin . The rest of the
proof is analogous and the details are left to the reader.
As we now must consider the objective function, we cannot simply apply Theorem 1 to [costconf-ILP]. However, we can prove a slightly weaker version by decomposing the ILP in several
smaller ones and applying the theorem to each of them.
Theorem 16. If [cost-conf-IP] is feasible, then there exists an optimal solution x satisfying:
P
2
3
1.
c∈Qc xc ∈ O((1/δ ) log (1/δ)), and
2. | supp(x) ∩ Qs | ∈ O((1/δ) log2 (1/δ)).

Proof. Notice that the load of each configuration π · c is a multiple of L/λ2 , and thus π · c ∈
{L/λ, L/λ + L/(λ2 ), . . . , 4L} . We classify the configurations according to their loads, Qℓ :=
{c ∈ Q : π · c = L/λ + ℓ · L/(λ2 )}, for ℓ ∈ {0, . . . , 4λ2 − λ}. Let x∗ be an optimal solution of
[cost-conf-IP]. Then we can considered an ILP for each load value ℓ:

12

X

[conf-IP]ℓ

c · xc =

c · x∗c ,

(4)

c∈Qℓ

c∈Qℓ

X

X

xc =

X

x∗c ,

(5)

c∈Qℓ

c∈Qℓ

for all c ∈ Qℓ .

xc ∈ Z≥0

(6)

Scaling π by multiplying it by λ2 /L we obtain an integral vector (since π is an integer multiple of L/(λ2 )), we can apply Theorem 1 to each ILP [conf-IP]ℓ , which yields that
P there exists
a thin solution xℓ . In particular the number of complex configurations in xℓ is c∈Qc ∩Qℓ xℓc ∈
O((1/δ) log2 (1/δ)). Since f¯c depends only on the load of c, concatenating
P these solutions
yields a solution x′ := (xℓ )ℓ that is optimal for [cost-conf-IP], such that c∈Qc x′c ∈ O((λ2 ) ·
(1/δ) log2 (1/δ)) = O((1/δ 3 ) log2 (1/δ)). It remains to bound the number of simple configurations
in the support. To this end, we consider the ILP restricted to simple configurations as follows:
[cost-conf-IP]s

min

X

f¯c · xc

c∈Qs

X

c · xc = b −

c∈Qs

X

X

c · x′c ,

(7)

c∈Qc

xc = m −

c∈Qs

xc ∈ Z≥0

X

x′c ,

(8)

c∈Qc

for all c ∈ Qs .

(9)

We apply the result of Eisenbrand and Shmonin [4] to this ILP. In its more general form,
this result ensures the existence of a solution x′′ with support of size O(N (log(N ) + ∆)), where
N is the number of restrictions and ∆ is the encoding size of the largest coefficient appearing
in the cost vector and restriction matrix. In our case N = d + 1 = O((1/δ) log(1/δ)), and
∆ = O(log(max{1/δ, maxc∈Q f¯c )}) = O(log(1/δ)) (Lemma 15). Thus O(N (log(N ) + ∆)) =
O((1/δ) log2 (1/δ)). The theorem follows by concatenating (x′′c )c∈Qs with (x′c )c∈Qc .
Finally, we use the structure given by the theorem to solve this ILP optimally.
Algorithm 17.
1. For each processing time πk , guess the number bck ≤ bk of jobs covered by complex configurations.
2. Guess the number mc of machines that schedule jobs bc .
3. Compute an optimal solution for instance with number of jobs bc on mc machines with a
dynamic program.
4. Guess the support of simple configurations Q̄s ⊆ Qs used by the solution implied by Theorem 1, with |Q̄s | ∈ O((1/δ) log2 (1/δ)).
5. Solve the ILP restricted to configurations in Q̄s :
X
min
f¯c · xc
c∈Qs

X

c · xc = b − bc ,

c∈Q̄s

X

xc = m − mc ,

c∈Q̄s

xc ∈ Z≥0

for all c ∈ Q̄s .
13

4

Lemma 18. Algorithm 17 can be implemented with a running time of 2O((1/δ) log

(1/δ))

log(n).

Proof. In step 1, the algorithm guesses which jobs are processed on machines following a complex configurations. Since each configuration contains at most O(1/δ) jobs, there are at most
O((1/δ 4 ) log2 (1/δ)) jobs assigned to such machines. For each size πk ∈ Π, we guess the number
bck of jobs of size πk assigned to such machines. Hence, we can enumerate all possibilities for
2
jobs assigned to complex machines in time 2O((1/δ) log (1/ε)) . Similarly, we can guess the number
2
of machines in step 2 since mc ∈ O((1/δ 3 ) log (1/δ)). For step 3 we use a simple dynamic
program that goes over the machines storing a table T (ℓ, z1 , . . . , zd ) that contains the minimum
cost achieved over the first ℓ ≤ mc machines with zk ≤ bck jobs of size πk . The number of
Qd
entries the table is O(mc k=1 (bck + 1)). Computing T (ℓ, z1 , . . . , zd ) can be done by checking
all entries of the type T (ℓ − 1, z1′ , . . . , zd′ ) for zk′ ≤ zk . Thus, the running time of the dynamic
Q
programm is O(mc [ dk=1 (bck + 1)]2 ). Since bck ∈ O((1/δ 4 ) log2 (1/δ)) for each k, recalling that
mc ∈ O((1/δ 3 ) log2 (1/δ)), and that d = |Π| ∈ O((1/δ) log(1/δ)), we obtain that step 3 can be
2
implemented with 2O((1/δ) log (1/δ)) running time.
In step 4, our algorithm guesses the support of the solution implied by Theorem 16. Let D
be the bound implied by the third property of this theorem, so that | supp(x) ∩ Qs | ≤ D and
2
D ∈ O((1/δ) log2 (1/δ)). Also, |Qs | ≤ 2O(log (1/δ)) Then the guessing in step 4 needs to consider
the following number of possibilities:

D 
X
|Qs |
i=0

i

≤ (D + 1)|Qs |D ≤ 2O((1/δ) log

4

(1/δ))

.

In step 5, the number of variables of the restricted ILP is |Q̄s | = O((1/δ) log2 (1/δ)). Moreover,
using Lemma 15 the size of the input can be bounded by O((1/δ 2 ) log3 (1/δ) log(n)). Running
3
Kannan’s algorithm [14] to solve the ILP takes time 2O((1/δ) log (1/δ)) log(n). Hence, the total
4
running time of our algorithm can be bounded by 2O((1/δ) log (1/δ)) log(n).
As in [2], the algorithm above can be easily adapted for objectives (II), (I’) and (III’) by suitably adapting the ILP. We leave the details to the reader. This suffices to conclude Theorem 19
Theorem 19. Consider the scheduling problem on parallel machines with objective functions (I),
(II) for f convex (respectively (I’) and (II’) for f concave). If f satisfies Condition 12 for 1/δ =
4
O(1/ε), then the problem admits an EPTAS with running time 2O((1/ε) log (1/ε)) + O(n log n).

5

Minimum makespan scheduling on uniform machines

In this section we generalize our result for P ||Cmax to uniform machines. Consider a set of jobs
J with processing times pj and a set of m non-identical machines M where machine i ∈ M runs
at speed si . If job j is executed on machine i the machine needs pj /si time units to complete
the job. The problem is to find
Pan assignment a : J → M for the jobs to the machines that
minimizes the makespan; maxi j:a(j)=i pj /si . The problem is denoted by Q||Cmax . We suppose
that s1 ≥ s2 ≥ . . . ≥ sm . Jansen [11] found an efficient polynomial time approximation scheme
2
3
(EPTAS) for this scheduling problem which has a running time of 2O(1/ε log (1/ε)) + poly(n).
Here we show how to improve the running time and prove the main result of this section.
Theorem 20. There is an EPTAS (a family of algorithms {Aε : ε > 0}) which, given an instance
I of Q||Cmax with n jobs and m machines and a positive number ε > 0, produces a schedule of
4
makespan Aε (I) ≤ (1 + ε)Opt(I). The running time of Aε is 2O(1/ε log (1/ε)) + poly(n).
We follow the approach by Jansen [11], transforming the scheduling problem into a bin
packing problem with different bin capacities, round the processing times and bin capacities,
divide the bins into at most three groups and generate four different scenarios depending on the
input instance.
First, we compute a 2-approximate solution using the algorithm by Gonzales et al. [6] of length
B(I) ≤ 2 Opt(I). Suppose that ε < 1; otherwise we can take the 2-approximate solution and
14

are done. Then we choose a value δ ∈ (0, ε) such that 1/δ is integral (the exact value is specified
later) and use a binary search within the interval [B(I)/2, B(I)] (that contains Opt(I)). We use
a standard dual approximation method that for each value T either computes an approximate
schedule of length T (1 + aδ) (where a is constant) or shows that there is no schedule of length T .
Since (δ/2)B(I) ≤ δOpt(I), we can find within O(log(1/δ)) iterations a value T ≤ Opt(I)(1+δ)
with a corresponding schedule of length at most T (1 + aδ) ≤ Opt(I)(1 + ε), using δ ≤ ε/(a + 2)
and ε ≤ 1. Next, the scheduling problem is transformed into a bin packing problem with m bins
and capacities ci = T · si , the processing times pj are rounded to the next value p̄j of the form
δ(1 + δ)kj with kj ∈ Z and the bin capacities are rounded to the next power of (1 + δ). We call
B the set of bins with rounded capacities.
Lemma 21 (Jansen [11]). If there is a feasible packing of n jobs with processing times pj into
m bins with capacities ci , then there is also a packing of n jobs with rounded processing times
p̄j = δ(1 + δ)kj ≤ (1 + δ)pj into m bins with rounded bin capacities c′i = (1 + δ)ℓi ≤ ci (1 + δ)2
with ℓi ∈ Z.
If the number m of bins is smaller than K ∈ O(1/δ log(1/δ)), then we can use an approximation scheme by Jansen and Mastrolilli [12] to compute an (1 + ε)-approximate solution to schedule n jobs on m unrelated machines (an even more general problem) within time
2
2
O(n) + 2O(m log(m/ε)) = O(n) + 2O(1/δ log (1/δ)) = O(n) + 2O(1/ε log (1/ε)) ; using that δ ∈ O(ε).
Suppose from now on that K > O(1/δ log(1/δ)). Then, we divide the bins into at most three
different bin groups. The first group B1 consists of the K = O(1/δ log(1/δ)) largest bins. For
some γ ∈ Θ(ε2 ), the next group B2 consists either of all the remaining bins {bK+1 , . . . , bm }
if c′m > γc′K (and we have only two bin groups) or B2 contains the next G largest bins
{bK+1 , . . . , bK+G } where G is the smallest index such that capacity c′K+G+1 ≤ γc′K . In the
second case, B3 = {bK+G+1, . . . , bm }. Let cmax (B) and cmin (B) be the largest and smallest bin
capacity in B. If cmax (B)/cmin (B) ≤ C for some value C and B contains only rounded capacities
(1 + δ)x with x ∈ Z, then the number of different capacities in B is at most O(1/δ log(C)).
Lemma 22 (Jansen [11]). If there is a solution for the original instance (J , M) of our scheduling
problem with makespan T and corresponding bin sizes, then there is a feasible packing for instance
(J , B1′ ∪ B2 ∪ B3 ) or instance (J , B1′ ∪ B2 ) with rounded bin capacities c̄i ≤ ci (1 + δ)3 and rounded
processing times p̄j ≤ (1 + δ)pj . Here B1′ is the subset of B1 with bins of capacity larger than
δ/(K − 1)cmax (B1 ) and B2 has a constant number O(1/δ log(1/δ)) of different bin capacities. In
addition we have one of the following four scenarios:
(1) Two bin groups B1′ and B2 with a gap cmin (B1′ )/cmax (B2 ) ≥ 1/δ.
(2) Two bin groups B1 and B2 with a constant number O(1/δ log(1/δ)) of different bin capacities
in B1′ ∪ B2 .
(3) Three bin groups B1′ , B2 , B3 with a gap cmin (B1′ )/cmax (B2 ) ≥ 1/δ and cmin (B1 )/cmax (B3 ) ≥
1/γ.
(4) Three bin groups B1′ , B2 , B3 with a constant number O(1/δ log(1/δ)) of different bin capacities in B1′ ∪ B2 and a gap cmin (B1 )/cmax (B3 ) ≥ 1/γ.
Notice that scenario 4 can be seen as a special case of scenario 3 by using B2new = B1 ∪ B2 ,
= ∅, and B3new = B3 . The same modification works to show that scenario 2 is a special case
of scenario 1. Finally, scenario 1 can be interpreted a special case of scenario 3, using B3 = ∅.
Therefore, it is sufficient to improve the running time for scenario 3.
Scenario 3 will be solved using a mix of dynamic programming and mixed integer linear
programming (MILP) techniques. In this approach we use only the larger bins in B1′ of B1 to
execute jobs, but in the rounding step for scenario 3 afterwards we may also use the smaller bins
in B1 . Notice that a packing into a bin bi with capacity c̄i ≤ ci (1 + δ)3 corresponds to a schedule
on machine i with total processing time at most c̄i /si ≤ T (1 + δ)3 . For T ≤ Opt(I)(1 + δ) this
gives us a schedule of length at most Opt(I)(1 + δ)4 .PIf there a feasible
Pm schedule with makespan
T , then the total processing time of the instance is j∈J pj ≤ i=1 c̄i . If this inequality does
B1new

15

not hold, then we discard the choice with makespan T . Otherwise, we can eliminate the set Jtiny
of tiny jobs with processing time ≤ δc̄m and pack them greedily at the end of the algorithm into
the enlarged bins of size c̄i (1 + δ). Hence, in what follows we assume that Jtiny is empty.

5.1

Solution for the instance (J , B1′ ∪ B2 ∪ B3 )

In this subsection we consider scenarios 3 above with three bin groups. First, we preassign all
huge jobs with processing time > δc̄K ′ into the first K ′ machines. Since c̄K+1 = cmax (B2 ) ≤
δcmin (B1′ ) = δc̄K ′ , the huge jobs fit only on the first K ′ bins. The number of huge jobs can
be bounded by O(Kcmax (B1 )/(δcK ′ )) = O(1/δ 4 log2 (1/δ)). If there are more huge jobs in the
instance, then there is no packing into B1′ ∪ B2 and we are done. Furthermore, the number of
machines K ′ ∈ O(1/δ log(1/δ)) is constant. Again, we can use the approximation scheme by
Jansen and Mastrolilli that computes an (1 + δ)-approximate schedule for N jobs on M machines
which runs in O(N ) + 2O(M log(M/δ)) . For M ∈ O(1/δ log(1/δ)) and N ∈ O(1/δ 4 log2 (1/δ)) this
2
2
gives a running time O(1/δ 4 log2 (1/δ)) + 2O(1/δ log (1/δ)) = 2O(1/δ log (1/δ)) to obtain a feasible
4
packing with bin sizes c̄i (1 + δ) or schedule of length ≤ T (1 + δ) , if one exists. If there is no
feasible packing for the huge jobs, then there is no schedule with makespan T and we have to
increase T in the binary search. In the other case we set up a MILP.
After the assignment of the huge jobs, we have a free area S0 in B1 for the remaining jobs
with processing time p̄j ≤ δc̄K ′ . The different bin capacities in B2 and B3 are denoted by
c̄(1) > . . . > c̄(L) and c̄(L + 1) > . . . > c̄(L + N ), respectively. Let mℓ be the number of bins of
size c̄(ℓ) for ℓ = 1, . . . , L + N . The mℓ machines of the same speed form a block Bℓ of bins with
the same capacity c̄(ℓ). In addition, we have n1 , . . . , nP jobs of size δ(1 + δ)kj and suppose that
the first P ′ ≤ P job sizes are larger than c̄K+1 = c̄(1).
(ℓ)
(ℓ)
In the MILP we use C1 , . . . , Chℓ as configurations or multisets with numbers δ(1 + δ)kj ∈
[δc̄(ℓ), c̄(ℓ)] (these are large processing times corresponding to block Bℓ ), where the total sum
P
(ℓ)
(ℓ)
(ℓ)
kj
is bounded by c̄(ℓ). Here a(kj , Ci ) is the number of
size(Ci ) =
j a(kj , Ci )δ(1 + δ)
(ℓ)

occurrences of number δ(1 + δ)kj in configuration Ci . In the MILP below, we use integral
(ℓ)
and fractional variables xi to indicate number of machines that are scheduled according to
(ℓ)
configuration Ci . In addition, we use fractional variables yj,ℓ to indicate the number of jobs
kj
of size δ(1 + δ) placed as small ones in block Bℓ ; i.e. δ(1 + δ)kj < δc̄(ℓ). For each job size
δ(1 + δ)kj ≤ c̄(1), let aj be the smallest index in {1, . . . , L + N } such that δ(1 + δ)kj ≥ δc̄(aj ).
If there is no such index, we have a tiny processing time δ(1 + δ)kj < δc̄(L + N ). Notice that
the first P ′ job sizes are within (c̄(1), δcK ′ ]. These jobs do not fit into B2 ∪ B3 . Therefore, for
these job sizes we use only one variable yj,0 = nj and set aj = 0.
P (ℓ)
x
Paj −1
Pi i
(ℓ) (ℓ)
yj,ℓ
ℓ,i a(kj , Ci )xi +
P ℓ=0
P
(ℓ) (ℓ)
size(Ci )xi + j:ℓ<aj yj,ℓ δ(1 + δ)kj
PiP
kj
j=1 yj,0 δ(1 + δ)
(ℓ)

xi integral ≥ 0
(ℓ)
xi ≥ 0
yj,0 = nj
yj,ℓ integral ≥ 0

for
for
for
for

≤ mℓ
for
= nj
for
≤ mℓ c̄(ℓ) for
≤ S0 ,

ℓ = 1, . . . , L + N,
j = P ′ + 1, . . . , P,
ℓ = 1, . . . , L + N,

ℓ = 1, . . . , L and i = 1, . . . , hℓ ,
ℓ = L + 1, . . . , L + N and i = 1, . . . , hℓ
j = 1, . . . , P ′ ,
j = P ′ + 1, . . . , P and ℓ = 0, . . . , aj − 1.

In the MILP above, we use integral variables for configurations in the blocks of group B2
and fractional variables for the configurations in blocks of B3 . Each feasible packing for the
jobs into the bins corresponds to a feasible solution of the MILP. The total number of variables
is O(n2 ) + O(n)2O(1/δ log(1/δ)) , the number of integral variables is at most 2O(1/δ log(1/δ)) , and
the number of constraints (not counting the non-negativity constraints) is at most O(n). The
previous approach to solve the scheduling problem and the underlying MILP had a running time
2
3
of 2O(1/δ log (1/δ)) + poly(n). In order to use an approach similar to the scheduling on identical
16

(ℓ)

machines, each large size δ(1 + δ)kj ∈ Ci is rounded up to the next multiple of δ 2 c̄(ℓ). This
(ℓ)
(ℓ)
(ℓ)
enlarges the size of each configuration Ci from size(Ci ) to at most size(Ci ) + δc̄(ℓ) and the
corresponding bin size from c̄(ℓ) to (1 + δ)c̄(ℓ).
(ℓ)
(ℓ)
Let C̄1 , . . . , C̄h̄ be the configurations of size at most (1 + δ)c̄(ℓ) with the rounded-up numℓ

(ℓ)

bers q(kj , ℓ)δ 2 c̄(ℓ) with q(kj , ℓ) ∈ Z+ and multiplicities a(kj , C̄i ). This rounding implies also
(ℓ)
that the rounded size size(C̄i ) of a configuration is a multiple of δ 2 c̄(ℓ). Each new rounded
(ℓ)
(ℓ)
configuration C̄i (with rounded-up numbers q(kj , ℓ)δ 2 c̄(ℓ) and multiplicities a(kj , C̄i )) corresponds to an integral point inside the knapsack polytope Pℓ = {C = (a(kj , C)) : q · C ≤
P
(ℓ)
(ℓ)
1/δ 2 + 1/δ} such that j q(kj , ℓ)a(kj , C̄i )δ 2 c̄(ℓ) = size(C̄i ) ≤ (1 + δ)c̄(ℓ) or, equivalently,
P
(ℓ)
2
2
j q(kj , ℓ)a(kj , C̄i ) ≤ 1/δ + 1/δ ≤ 2/δ . We consider now a modified MILP with configura(ℓ)

(ℓ)

tions C̄i and coefficients a(kj , C̄i ). Note that the total area of all configurations in Bℓ can be
P (ℓ)
P
P
(ℓ) (ℓ)
(ℓ) (ℓ)
bounded by i size(C̄i )xi ≤ i size(Ci )xi + δc̄(ℓ) i xi . This, together with the small
P
P
P
(ℓ) (ℓ)
(ℓ) (ℓ) P
jobs gives i size(C̄i )xi + j δ(1+δ)kj yj,ℓ ≤ i size(Ci )xi +δmℓ c̄(ℓ)+ j δ(1+δ)kj yj,ℓ ≤
mℓ c̄(ℓ)(1 + δ); i.e. the total area is increased by at most a multiplicative factor of (1 + δ). Since
the total area of all jobs within one block is increased by this rounding, we use the following new
constraints in the modified MILP:
X
X
(ℓ) (ℓ)
for ℓ = 1, . . . , L.
yj,ℓ δ(1 + δ)kj ≤ mℓ c̄(ℓ)(1 + δ)
size(C̄i )xi +
j

i

Next, we divide the coefficients in the L area constraints above by δ 2 c̄(ℓ). Then the coefficients of
(ℓ)
(ℓ)
the xi variables are now size(C̄i )/(δ 2 c̄(ℓ)) = ai,ℓ δ 2 c̄(ℓ)/(δ 2 c̄(ℓ)) = ai,ℓ ∈ {1/δ, . . . , 1/δ 2 + 1/δ}.
Using the assumption that 1/δ is integral, all coefficients of the variables are integral and bounded
by 2/δ 2 . Notice that increasing the capacities of all bins and dividing all coefficients as above,
implies also a feasible solution of the modified MILP. Let us study a feasible solution of the
modified MILP. To reduce the number of integral configuration variables in the MILP, we consider
(ℓ)
the following ILP that uses only the integral xi variables within bin group B2 :
X

(ℓ)

xi

= m̄ℓ

for ℓ = 1, . . . , L,

(10)

i

X

(ℓ)

(ℓ)

= n̄j

for j ∈ P (B2 ),

(11)

(ℓ)

= Area(ℓ, large)

for ℓ = 1, . . . , L,

(12)

for i = 1, . . . , h̄ℓ , ℓ = 1, . . . , L.

(13)

a(kj , C̄i )xi

ℓ,i

X size(C̄ (ℓ) )
i

i
(ℓ)
xi

δ 2 c̄(ℓ)

xi

integral ≥ 0

where the values m̄ℓ , n̄j , and Area(ℓ, large) are given by a feasible solution of the modified
MILP. Here P (B2 ) is the set of all indices of large job sizes corresponding to blocks Bℓ ∈ B2 ;
i.e. P (B2 ) = {j : δ(1 + δ)kj ∈ (δc̄(L), c̄(1)]}. The cardinality of P (B2 ) and the value L can be
bounded by O(1/δ log(1/δ)). All the coefficients above of the variables are bounded by O(1/δ 2 ).
(ℓ)
(ℓ)
(ℓ)
The support of a configuration C̄i is the number of values a(kj , C̄i ) > 0; i.e. supp(C̄i ) =
(ℓ)
(ℓ)
(ℓ)
|{j : a(kj , C̄i ) > 0}|. In our case supp(C̄i )) ≤ O(1/δ log(1/δ)). A configuration C̄i is called
(ℓ)
(ℓ)
simple, if | supp(C̄i )| ≤ log(1/δ 2 + 1/δ + 1) Otherwise, we call a configuration C̄i complex.
Using the result by Eisenbrand and Shmonin, we can find a feasible solution of the ILP above (if
there is a feasible solution of the modified MILP) with at most O(1/δ log2 (1/δ)) many variables
(ℓ)
(ℓ)
xi > 0; i.e. | supp(x)| ≤ O(1/δ log2 (1/δ)) where x = (xi ). We can generalize our result in
Theorem 1 to our ILP above.
Lemma 23. Assume that the ILP defined by (10)-(13) is feasible and let S denote the set of all
simple configurations. Then there exists a feasible solution x′ such that:
(ℓ)

(1) If x′ i

(ℓ)

> 1 then the configuration C̄i

is simple.
17

(2) The support of x′ satisfies | supp(x′ ) ∩ S| ∈ O(1/δ log2 (1/δ)).
(3) The support of x′ satisfies | supp(x′ ) \ S| ∈ O(1/δ 2 log3 (1/δ)).
(ℓ)

(ℓ)

Proof. As stated above, the set of configurations C̄1 , . . . , C̄h̄ equals the set of integral points
ℓ
Qℓ inside the knapsack polytope Pℓ = {C = (q(kj , C)) : q · C ≤ 1/δ 2 + 1/δ} Let x̄ = (x̄(ℓ) )L
ℓ=1
be a solution to (10)-(13) where x̄(ℓ) corresponds to the variables defining the solution for block
Bℓ . We consider a family of ILPs defined for each ℓ = 1, . . . , L.
X
X
c · xc =
[conf-IP]ℓ
c · x̄(ℓ)
c ,
c∈Qℓ

X

c∈Qℓ

xc = m̄ℓ ,

c∈Qℓ

xc ∈ Z≥0

for all c ∈ Qℓ .

Using Theorem 1 for each [conf-IP]ℓ , we obtain new solution x̂(ℓ) , where each complex configuration is used at most once and supp(x̂(ℓ) ) ∈ O(1/δ log2 (1/δ)). Then we define a new solution x̂
of ILP (10)-(13) defined as (x̂(ℓ) )ℓ . In x̂ every complex configuration is used at most once and
| supp(x̂)| ≤ L · 2(d¯ + 1) log(4(d¯ + 1)T̄ ) ∈ O(1/δ 2 log3 (1/δ)), where d¯ ≤ |P (B2 )| ∈ O(1/δ log 1/δ)
and T̄ ∈ O(1/δ 2 ). Note that Equation (12) of the above ILP holds for the new solution x̂ as the
set of jobs covered inside a block does not change and hence
X size(C̄ (ℓ) )
i

i

δ 2 c̄(ℓ)

(ℓ)

x̂i

= Area(ℓ, large) =

X size(C̄ (ℓ) )
i

i

δ 2 c̄(ℓ)

(ℓ)

x̄i .

(ℓ)

Finally, consider the ILP (10)-(13) and fix each variable xℓi , for C̄i a complex configuration,
to the value x̂ℓi (and thus the resulting ILP has variables only for simple configurations). Now
we can apply the result of Eisenbrand and Shmonin [4] to this ILP. This ensures that any ILP of
the form {z ∈ Z≥0 : Az = h} admits a solution with support of size O(N (log(N ) + ∆)), where
N is the number of rows of A and ∆ is the largest encoding size of an entry of A. Recalling that
(ℓ)

size(C̄i )
δ 2 c̄(ℓ)

∈ O(1/δ 2 ), we can apply this result to our case, which yields a solution whose support

contains at most O(1/δ log2 (1/δ)) simple configurations. Hence, we obtain a solution satisfying
all properties of the statement of the theorem.
Algorithm 24.
1. For each job size, guess the number of jobs vj ≤ n̄j covered by complex configurations.
2. For each bin size, guess the number of machines wj ≤ m̄j used to schedule the set of jobs
covered by complex configurations.
(ℓ)

(ℓ)

3. For each block ℓ in B2 , guess the support of simple configurations Q̄s ⊆ Qs used by a
P
(ℓ)
2
thin solution, with L
ℓ=1 |Q̄s | ≤ 4(d + 1) log(4(d + 1)T̄ ) ∈ O((1/ε) log (1/ε)).

4. Solve the reduced modified MILP, where the integral variables xℓi are restricted to simple
configurations.
Lemma 25. Algorithm 24 can be implemented with a running time of 2O((1/ε) log

4

(1/ε))

poly(n).

Proof. As in the case of identical machines, our algorithm guesses in step 1 the complex configurations and the corresponding jobs. Since the number M of complex configurations within B2
ist at most O(1/δ 2 log3 (1/δ)) and there are at most O(1/δ) many large job per configuration,
the total number N of jobs within the complex configurations is at most O(1/δ 3 log3 (1/δ)).
To obtain a schedule for the guessed jobs, notice that the number of large job sizes |P (B2 )| ≤
O(1/δ log(1/δ)). We guess now a vector v = (vj ) with possible job sizes that are covered by the
complex configurations. The total number of these vectors is (N +1)|P (B2 )| ≤ (1/δ 3 log3 (1/δ))O(1/δ log(1/δ)) =
18

2

2O(1/δ log (1/δ)) . In addition, we guess a vector w = (wℓ ) with the numbers wℓ of complex
configurations in the block groups Bℓ . The number of choices here is at most (M + 1)L ≤
2
(1/δ 2 log3 (1/δ))O(1/δ log(1/δ)) = 2O(1/δ log (1/δ)) . For each guess v, w we run a dynamic program
to test whether the number of job sizes, stored in v, fit on the corresponding machines in the
blocks Bℓ , given by vector w. To do this, we run over the machines and store after ℓ machines,
for ℓ = 1, . . . , M , the set of all feasible vectors with job sizes that can be packed into the first
2
2
ℓ machines. This dynamic program runs in time M 2O(1/δ log (1/δ)) = 2O(1/δ log (1/δ)) . For each
feasible choice of v, w we compute the reduced MILP by m̂ℓ = mℓ − wℓ and n̂j = nj − vj and
guess the support of a feasible solution x in the MILP; i.e. the simple configurations in B2 with
(ℓ)
(ℓ)
value xi > 0. The total number of simple configurations Qs in one bin block can be bounded,
2
using observation 7, by 2O(log (1/δ)) . Therefore, the total number of simple configurations in B2
PL
2
2
(ℓ)
is ℓ=1 |Qs | ≤ L · 2O(log (1/δ)) = 2O(log (1/δ)) . This implies that the number of choices for the
support of x is at most
 

2
(ℓ)
|Qs |
4
2O(log (1/δ))
=
= 2O(1/δ log (1/δ)) .
O(1/δ log2 (1/δ))
O(1/δ log2 (1/δ))



P

ℓ

For each choice we solve a reduced MILP with d = O(1/δ log2 (1/δ)) integral variables (step
4). The total size s of the MILP can be bounded by s ≤ poly(n, 1/δ) + n log(n)2O(1/δ log(1/δ)) .
Using the algorithm by Kannan with runnning time dO(d) poly(s) for an MILP with d variables
3
and size s, we obtain a running time to solve one MILP in time 2O(1/δ log (1/δ)) poly(n); using
poly(s) ≤ poly(n)2O(1/δ log(1/δ)) . Running over all vectors v, w and all guesses for the simple
4
configurations, we obtain a running time of 2O(1/δ log (1/δ)) + poly(n).
The rounding of the fractional variables in the MILP solutions and the packing of the items
accordingly works as in [11] and can be done in time 2O(1/δ log(1/δ)) poly(n). Therefore, the
4
overall running time of the entire algorithm can be bounded by 2O(1/δ log (1/δ)) + poly(n) =
4
2O(1/ε log (1/ε)) + poly(n); using that δ ∈ O(ε).
In order to calculate the length of the computed schedule and to specify δ, we use the following
result:
Lemma 26. [11] If there is a feasible solution of an MILP instance with bin capacities c̄(ℓ) for
blocks Bℓ ∈ B2 ∪ B3 and capacities c̄i for the K largest bins in B1 , then the entire job set J can
be packed into bins with capacities c̄(ℓ)(1 + 2δ)2 for blocks Bℓ ∈ B2 ∪ B3 and enlarged capacities
c̄i (1 + 3δ)2 for the first K bins.
Note that the result above is constructive, too. This means that there is also an algorithm
that computes a corresponding packing [11]. Using c̄i ≤ ci (1 + δ)3 and T ≤ (1 + δ)OP T and
the lemma above, we can bound the schedule length. If there is a schedule with length at most
T and with corresponding bin sizes ci = T si , then the lemma above implies a packing into
bins of size ci (1 + 3δ)3 (1 + 3δ)2 and a corresponding schedule length ≤ T (1 + δ)3 (1 + 3δ)2 ≤
1
OP T (1 + δ)4 (1 + 3δ)2 ≤ OP T (1 + 16δ) ≤ OP T (1 + ε) for δ ≤ ε/16 and ε ≤ 1. Using δ = ⌈16/ε⌉
,
we obtain δ ≤ ε/16, δ ≥ ε/17, and that 1/δ = ⌈16/ε⌉ is integral. This concludes the proof for
Theorem 20.

References
[1] N. Alon, Y. Azar, G. Woeginger, and T. Yadid. Approximation schemes for scheduling. In
Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’97,
pages 493–500, 1997.
[2] N. Alon, Y. Azar, G. J. Woeginger, and T. Yadid. Approximation schemes for scheduling
on parallel machines. Journal of Scheduling, 1:55–66, 1998.
[3] L. Chen, K. Jansen, and G. Zhang. On the optimality of approximation schemes for the
classical scheduling problem. In Proceedings of the 25th Annual ACM-SIAM Symposium
19

on Discrete Algorithms (SODA 2013), pages 657–668. Society for Industrial and Applied
Mathematics, 2013.
[4] F. Eisenbrand and G. Shmonin. Carathéodory bounds for integer cones. Operations Research
Letters, 34:564–568, 2006.
[5] M. X. Goemans and T. Rothvoß. Polynomiality for bin packing with a constant number
of item types. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA ’14), pages 830–839, 2014.
[6] T. F. Gonzalez, O. H. Ibarra, and S. Sahni. Bounds for LPT schedules on uniform processors.
SIAM Journal on Computing, 6(1):155–166, 1977.
[7] R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal,
45:1563–1581, 1966.
[8] R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied
Mathematics, 17:416–429, 1969.
[9] D. Hochbaum, editor. Approximation algorithms for NP-hard problems. PWS Publishing
Company, 1997.
[10] D. S. Hochbaum and D. B. Shmoys. Using dual approximation algorithms for scheduling
problems: theoretical and practical results. Journal of the ACM, 34:144–162, 1987.
[11] K. Jansen. An EPTAS for scheduling jobs on uniform processors: Using an MILP relaxation
with a constant number of integral variables. SIAM Journal on Discrete Mathematics,
24:457–485, 2010.
[12] K. Jansen and M. Mastrolilli. Scheduling unrelated parallel machines: linear programming
strikes back. University of Kiel, Technical Report, (1004), 2010.
[13] K. Jansen and C. Robenek. Scheduling jobs on identical and uniform processors revisited.
In R. Solis-Oba and G. Persiano, editors, Approximation and Online Algorithms, number
7164 in Lecture Notes in Computer Science, pages 109–122. 2011.
[14] R. Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of
Operations Research, 12:415–440, 1987.
[15] H. W. Lenstra. Integer programming with a fixed number of variables. Mathematics of
Operations Research, 8:538–548, 1983.
[16] J. Y-T. Leung. Bin packing with restricted piece sizes. Information Processing Letters,
31:145–149, 1989.

20

