Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios
Christos Kalaitzis∗

Ola Svensson∗

Jakub Tarnawski∗

arXiv:1607.07631v2 [] 3 Nov 2016

November 4, 2016

Abstract
We consider the classic problem of scheduling jobs on unrelated machines so as to minimize
the weighted sum of completion times. Recently, for a small constant ε > 0, Bansal et al.
gave a (3/2 − ε)-approximation algorithm improving upon the “natural” barrier of 3/2 which
follows from independent randomized rounding. In simplified terms, their result is obtained by
an enhancement of independent randomized rounding via strong negative correlation properties.
In this work, we take a different approach and propose to use the same elegant rounding
scheme for the weighted completion time objective as devised by Shmoys and Tardos for optimizing a linear function subject to makespan constraints. Our main result is a 1.21-approximation
algorithm for the natural special case where the weight of a job is proportional to its processing
time (specifically, all jobs have the same Smith ratio), which expresses the notion that each unit
of work has the same weight. In addition, as a direct consequence of the rounding, our algorithm
also achieves a bi-criteria 2-approximation for the makespan objective. Our technical contribution is a tight analysis of the expected cost of the solution compared to the one given by the
Configuration-LP relaxation – we reduce this task to that of understanding certain worst-case
instances which are simple to analyze.

∗

School of Computer and Communication Sciences, EPFL.
Email: {christos.kalaitzis,ola.svensson,jakub.tarnawski}@epfl.ch.
Supported by ERC Starting Grant 335288-OptApprox.

1

Introduction

We study the classic problem of scheduling jobs on unrelated machines so as to minimize the
weighted sum of completion times. Formally, we are given a set M of machines, and a set J of
jobs, each with a weight wj ≥ 0, such that the processing time (also called size) of job j on machine
i isPpij ≥ 0. The objective is to find a schedule which minimizes the weighted completion time, that
is j∈J wj Cj , where Cj denotes the completion time of job j in the constructed schedule.
P In the
three-field notation used in scheduling literature [GLLK79], this problem is denoted as R|| wj Cj .
The weighted completion time objective, along with makespan and flow time minimization,
is one of the most relevant and well-studied objectives for measuring the quality of service in
scheduling. Already in 1956, Smith [Smi56] showed a simple rule for minimizing this objective on a
single machine: schedule the jobs in non-increasing order of wj /pj (where pj denotes the processing
time of job j on the single machine). This order is often referred to as the Smith ordering of the jobs
and the ratio wj /pj is called the Smith ratio of job j. In the case of parallel machines, the problem
becomes significantly harder. Already for identical machines (the processing time of a job is the
same on all machines), it is strongly NP-hard, and for the more general unrelated machine model
that we consider, the problem is NP-hard to approximate within 1 + ε, for a small ε > 0 [HSW01].
Skutella and Woeginger [SW99b] settled the approximability for identical machines by developing a polynomial time approximation scheme. That is, for every ε > 0, they gave a (1 + ε)approximation algorithm for minimizing the weighted sum of completion times on identical parallel
machines.
In contrast, it remains a notorious open problem in scheduling theory to settle the approximability in the unrelated machine model (see e.g. “open problem 8” in [SW99a]). First, Schulz and
Skutella [SS02] and independently Chudak [Chu99] came up with (3/2 + ǫ)-approximation algorithms, employing a time-indexed LP relaxation for the problem. Shortly thereafter, the approximation guarantee was improved to 3/2 by Skutella [Sku01] and Sethuraman and Squillante [SS99]
using a clever convex quadratic programming relaxation. All these results relied on designing a
convex relaxation and then applying independent randomized rounding with the marginal probabilities that were returned by the convex relaxation solution. The analysis of these algorithms is
in fact tight: it is not hard to see that any algorithm using independent randomized rounding cannot achieve a better approximation guarantee than 3/2. Recently, Bansal et al. [BSS16] overcame
this barrier by designing a randomized rounding scheme that, informally, enhances independent
randomized rounding by introducing strong negative correlation properties. Their techniques yield
a (3/2 − ε)-approximation algorithm with respect to either a semidefinite programming relaxation
introduced by them or the Configuration-LP relaxation introduced in [SW13]. Their rounding and
analysis improve and build upon methods used previously for independent randomized rounding.
So a natural question motivating this work is: can a different rounding approach yield significant
improvements of the approximation guarantee?

1.1

Our results

Departing from previous rounding approaches, we propose to use the same elegant rounding scheme
for the weighted completion time objective as devised by Shmoys and Tardos [ST93] for optimizing
a linear function subject to makespan constraints on unrelated machines. We give a tight analysis
which shows that this approach gives a significantly improved approximation guarantee in the
special case where the Smith ratios of all jobs that can be processed on a machine are uniform:

1

that is, we have pij ∈ {wj , ∞} for all i ∈ M and j ∈ J .1
This restriction, which has not been studied previously, captures the natural notion that any
unit of work (processing time) on a fixed machine has the same weight. It corresponds to the
class of instances where P
the order of jobs on a machine does not matter. Compared P
to another
natural restriction of R|| wj Cj – namely, the unweighted sum of completion times R|| Cj – it is
both computationally harder (in fact, whereas the unweighted version is polynomial-time solvable
[Hor73, BCS74], our problem inherits all the known hardness characteristics of the general weighted
version: see Section 1.2) and more intuitive (it is reasonable to expect that larger jobs have larger
significance). Despite the negative results, our main theorem indicates that we obtain far better
understanding of this version than what is known for the general case.
To emphasize that we are considering the casePwhere the weight of a job is proportional to its
processing time, we refer to this problem as R|| pj Cj (with pj as opposed to wj ). With this
notation, our main result can be stated as follows:
√

Theorem
1.1. For any small ε > 0, there exists a 1+2 2 + ε < 1.21-approximation algorithm for
P
R|| pj Cj . Moreover, the analysis is tight:
there exists an instance for which our algorithm returns
√
1+ 2
a schedule with objective value at least 2 − ε times the optimum value.
We remark that the ε in the approximation guarantee arises because we can only solve the
Configuration-LP relaxation (see Section 2) up to any desired accuracy.
Interestingly enough, a similar problem (namely, scheduling jobs with uniform Smith ratios on
identical parallel machines) was studied by Kawaguchi and Kyan [KK86].2 They achieve the same
approximation ratio as we do, by using ideas in a similar direction as ours to analyze a natural
heuristic algorithm.
As we use the rounding algorithm by Shmoys
is that our
√ and Tardos, a pleasant side-effect
P
pj Cj objective
algorithm can also serve as a bi-criteria (1 + 2)/2 + ε-approximation for the
and 2-approximation for the makespan objective.3 This bi-objective setting was previously studied
by Kumar et al. [KMPS09], who gave a bi-criteria 3/2-approximation for the general weighted
completion time objective and 2-approximation for the makespan objective.
Our main technical contribution is a tight analysis of the algorithm with respect to the strong
Configuration-LP relaxation. Configuration-LPs have been used to design approximation algorithms for multiple important allocation problems, often with great success; therefore, as first
noted by Sviridenko and Wiese
P [SW13], they constitute a promising direction to explore in search
for better algorithms for R|| wj Cj . We hope that our analysis can give further insights as to how
the Configuration-LP can be used to achieve this.
On a high level, our analysis proceeds as follows. A fractional solution to the ConfigurationLP defines, for each machine, a local probability distribution of the set of jobs (configuration)
that will be processed by that machine. At the same time, the rounding algorithm (naturally)
produces a global distribution over such assignments, which inherits certain constraints on the
local distribution for each machine. Therefore, focusing on a single machine, we will compare
1

This restriction could be seen as close to the restricted assignment problem. However, we remark that all our
results also apply to the more general (but also more notation-heavy) case where the weight of a job may also depend
on the machine. A general version of our assumption then becomes pij ∈ {αi wij , ∞} for some machine-dependent
αi > 0. Our results apply to this version because our analysis will be done locally for each machine i, and therefore
we will only require that the Smith ratios be uniform for each machine separately.
2
We would like to thank the anonymous SODA 2017 reviewer for bringing this work to our attention.
3
More precisely, given any makespan threshold T > 0, our algorithm will return
√ a schedule with makespan at most
2T + ε and cost (i.e., sum of weighted completion times) within a factor (1 + 2)/2 + ε of the lowest-cost schedule
among those with makespan at most T .

2

the local input distribution (i.e., the one defined by the Configuration-LP) to the worst possible
(among ones satisfying said constraints) local output distribution that could be returned by our
randomized rounding.4 In order to analyze this ratio, we will have both distributions undergo
a series of transformations that can only worsen the guarantee, until we bring them into such a
form that computing the exact approximation ratio is possible. As the final form also naturally
corresponds to a scheduling instance, the tightness of our analysis follows immediately.

1.2

Lower Bounds and Hardness

P
All the known hardness features of the general problem R|| wj Cj transfer to our version
P
R|| pj Cj .
First, it is implicit in the work of Skutella
that both problems are APX-hard.5
√
Furthermore, complementing the (1+ 2)/2 upper bound on the integrality gap of the ConfigurationLP which follows from our algorithm, we have the following lower bound, proved in Section 5:
P
Theorem 1.2. The integrality gap of the Configuration-LP for R|| pj Cj is at least 1.08.
P
Finally, recall that the 32 -approximation algorithms for the general problem R|| j wj Cj by
Skutella [Sku01] and by Sethuraman and Squillante [SS99] are based on independent randomized
rounding of a fractional solution to a convex programming relaxation. It was shown by Bansal et
al. [BSS16] that this relaxation has an integrality gap of 23 and that, moreover, no independent
randomized rounding algorithm can have an approximation ratio better than 32 . We note that
both of these claims also apply to our version. Indeed, the integrality gap example of Bansal et
al. can be modified by having the job of size k2 and weight 1 instead have size k and weight k
(see [BSS16, Claim 2.1]). For the second claim, their problematic instance already has only unit
sizes and weights. Thus, to get better than 23 -approximation to our version, one can use neither
independent randomized rounding nor the relaxation of [Sku01, SS99].

1.3

Outline

The paper is structured as follows. In Section 2, we start by defining the Configuration-LP. Then,
in Section 3, we describe the randomized rounding algorithm by Shmoys and Tardos [ST93] applied
to our setting. We analyze it Section 4. Finally, in Section 5 we present the proof of the lower
bound on the integrality gap.

2

The Configuration-LP

As we are considering the case where pij ∈ {wj , ∞}, we let pj = wj . We further let Ji = {j ∈ J :
pij = pj } denote the set of jobs that can be assigned to machine i ∈ M.
For intuition, consider an optimal schedule of the considered instance. Observe that the schedule
partitions the jobs into |M| disjoint sets J = C1 ∪C2 ∪· · ·∪C|M|, where the jobs in Ci are scheduled
on machine i (so Ci ⊆ Ji ). As described in the introduction, the jobs in Ci are scheduled in an
optimal way on machine i by using a Smith ordering and, since we are considering the case where
4

For example, if we consider all distributions that assign 2 jobs to a machine, each with probability 1/2, then the
distribution which assigns either both jobs together or no job at all, each with probability 1/2, is the worst possible
distribution, i.e., the one that
P maximizes the expected cost.
5
APX-hardness for R|| wj Cj was first proved by Hoogeveen et al. [HSW01]. Skutella [Sku01, Section 7] gives a
different proof, where the reduction generates instances with all jobs having weights equal to processing times.

3

all jobs have the same Smith ratio, any ordering is optimal. The cost of scheduling the set of jobs
Ci on machine i can therefore be written as
X
X pj pj ′
.
cost(Ci ) =
p2j +
2
′
j6=j ∈Ci

j∈Ci

To see this, note thatP
if we pick a random schedule/permutation of Ci , then the expected
completion
P
pj ′
time of job j is pj + j ′ 6=j∈Ci 2 . The total cost of the considered schedule is i∈M cost(Ci ).
The Configuration-LP models, for each machine, the decision of which configuration (set of
jobs) that machine should process. Formally, we have a variable yiC for each machine i ∈ M and
each configuration C ⊆ Ji of jobs. The intended meaning of yiC is that it takes value 1 if C is the
set of jobs that machine i processes, and it takes value 0 otherwise. The constraints of a solution are
that each machine should process at most one configuration and that each job should be processed
exactly once. The Configuration-LP can be compactly stated as follows:
X X
min
yiC cost(C)
i∈M C⊆Ji

s.t.

X

C⊆Ji

X

X

yiC ≤ 1

∀i ∈ M ,

yiC = 1

∀j ∈ J ,

yiC ≥ 0

∀i ∈ M, C ⊆ Ji .

i∈M C⊆Ji :j∈C

This linear program has an exponential number of variables and it is therefore non-trivial to solve;
however, Sviridenko and Wiese [SW13] showed that, for any ε > 0, there exists a polynomial-time
algorithm that gives a feasible solution to the relaxation whose cost is at most a factor (1 + ε) more
than the optimum. Hence, the Configuration-LP becomes a powerful tool that we use to design a
good approximation algorithm for our problem.

3

The Rounding Algorithm

Here, we describe our approximation algorithm. We will analyze it in the next section, yielding
Theorem 1.1. The first step of our algorithm is to solve the Configuration-LP (approximately)
to obtain a fractional solution y ⋆ . We then round this solution in order to retrieve an integral
assignment of jobs to machines. The rounding algorithm that we employ is the same as that used
by Shmoys and Tardos [ST93] (albeit applied to a fractional solution to the Configuration-LP,
instead of the so-called Assignment-LP). For completeness, we describe the rounding scheme in
Algorithm 1; see also Figure 1.
P
⋆ . Intuitively, x denotes the marginal probability
The first step is to define xij = C⊆Ji :j∈C yiC
ij
⋆ . Note that, by the constraint that y ⋆
that job j should be assigned to machine i, according
to
y
P
assigns each job once (fractionally), we have i∈M xij = 1 for each job j ∈ J .
In the next steps, we round the fractional solution randomly so as to satisfy these marginals, i.e.,
so that the probability that job j is assigned toPi is xij . In addition, the number of jobs assigned
to a
P
machine
i
will
closely
match
the
expectation
x
:
our
rounding
will
assign
either
⌊
x
ij
j∈J
j∈J ij ⌋
P
P
or ⌈ j∈J xij ⌉ jobs to machine i. This is enforced by creating ⌈ j∈J xij ⌉ “buckets” for each
machine i, and then matching the jobs to these buckets. More formally, this is modeled by the
complete bipartite graph G = (U ∪V, E) constructed in Step 2 of Algorithm 1, where vertex ui,t ∈ U
corresponds to the t-th bucket of machine i.
4

Input : Solution y ⋆ to the Configuration-LP
Output: Assignment of jobs to machines
P
⋆ .
yiC
1) Define x ∈ RM×J as follows: xij =
C⊆Ji :j∈C

2) Let G = (U ∪ V, E) be the complete bipartite graph where

• the right-hand side consists of one vertex for each job j, i.e., V = {vj : j ∈ J },
P
xij ⌉ vertices for each machine i, i.e.,
• the left-hand side consists of ⌈
j∈J
P
S
xij ⌉}.
{ui,t : 1 ≤ t ≤ ⌈
U=
j∈J

i∈M

3) Define a fractional solution z to the bipartite matching LP for G (initially set to z = 0)
by repeating the following procedure for every machine i ∈ M:
P
• Let k = ⌈ j∈J xij ⌉, and let t be a variable originally set to 1.
• Iterate over all j ∈ J in non-increasing order in terms of pj :
P
If xij +
zui,t vj′ ≤ 1, then set zui,t vj = xij .
j ′ ∈J

Else, set zui,t vj = 1 −

P

j ′ ∈J

zui,t vj′ , increment t, and set zui,t vj = xij − zui,t−1 vj .

P
4) Decompose z into a convex combination of integral matchings z = t λt zt and sample
one integral matching z ∗ by choosing the matching zt with probability λt .
P
xij ⌉.
5) Schedule j ∈ J on i ∈ M iff zu∗i,t vj = 1 for some 1 ≤ t ≤ ⌈
j∈J

Algorithm 1: Randomized rounding

Observe that any integral matching in G that matches all the “job” vertices in V naturally
corresponds to an assignment of jobs to machines. Now, Step 3 prescribes a distribution on such
matchings by defining a fractional matching z. The procedure is as follows: for each machine i,
we iterate over the jobs j ∈ J in non-increasing order in terms of their size, and we insert items
of size xij into the first bucket until adding the next item would cause the bucket to become full;
then, we split that item between the first bucket and the second, and we proceed likewise for all
jobs until we fill up all buckets (except possibly for the last bucket). Having completed this process
for all machines i, we end up with a fractional matching z in G with the following properties:
P
• Every “job” vertex vj ∈ V is fully matched in z, i.e., i,t zui,t vj = 1.
P
P
• For every “bucket” vertex ui,t ∈ U , we have j zui,t vj ≤ 1, with equality if t < ⌈ j xij ⌉.
P
• The fractional matching preserves the marginals, i.e., xij = t zui,t vj for all j ∈ J and i ∈ M.
• We have the following bucket structure: if zui,t vj > 0 and zui,t′ vj′ > 0 with t′ > t, then
pj ≥ pj ′ .

The last property follows because Step 3 considered the jobs in non-increasing order of their processing times; this will be important in the analysis (see the last property of Fact 4.4).
Now, we want to randomly select a matching for G which satisfies the marginals of z (remember
that such a matching corresponds to an assignment of all the jobs to machines). We know that the
bipartite matching LP is integral and that z is a feasible solution for the bipartite matching LP
of G; therefore, using an algorithmic version of Carathéodory’s theorem (see e.g. Theorem 6.5.11
5

Input distribution on
configurations (patterns)
of machine i⋆ (y in
g)

Fractional matching

Bucketing of machine i⋆

2/3
1/3

⇒
0

1/3 2/3

⇒
2/3

1

1/3

2/3

2/3

2/3
1/3

1/3

1/3
1/3

1st bucket 2nd bucket 3rd bucket

⇓
1/3

×

+

1/3

×

+

1/3

×

⇐
0

1/3 2/3

1

Output distribution on
configurations (patterns)
of machine i⋆ (y out
f)

Combination of matchings

Figure 1: A sample execution of our rounding algorithm, restricted to a single machine i⋆ . Jobs
are represented by a rectangle; its height is the job’s processing time and its width is its
fractional assignment to i⋆ . Starting from an input distribution over configurations for
i⋆ , we extract the fractional assignment of each job to i⋆ , we create a bipartite graph
consisting of 3 copies of i⋆ and the jobs that are fractionally assigned to it, and then
we connect the jobs to the copies of i⋆ by iterating through the jobs in non-increasing
order of pj . Finally, we decompose the resulting fractional matching into a convex
combination of integral matchings and we sample one of them. The shown output
distribution is a worst-case distribution in the sense of Section 4.2: it maximizes the
variance of makespan, subject to the marginal probabilities and the bucket structure
enforced by the algorithm.
P
in [GLS93]), we can decompose z into a convex combination z = t λt zt of polynomially many
integral matchings, and sample the matching zt with probability λt . Then, if z ∗ is the matching
we
P
have sampled, we simply assign job j to machine i iff zu∗i,t vj = 1 for some t. Since xij = t zui,t vj
P
and i∈M xij = 1 for all jobs j, z ∗ will match all “job” vertices.6 The above steps are described
in Steps 4 and 5 of Algorithm 1.
The entire rounding algorithm is depicted in Figure 1.
6

We remark that this is the only part of the algorithm that employs randomness; in fact, we can derandomize the
algorithm by choosing the matching zk that minimizes the cost of the resulting assignment.

6

4

Analysis

⋆
Throughout the analysis, we fix a single machine
√ i ∈ M. We will show that the expected cost
of our algorithm on this machine is at most 1+2 2 times the cost of the Configuration-LP on this
machine. This clearly implies (by linearity
of expectation) that the expected cost of the produced
√
1+ 2
solution (on all machines) is at most 2 times the cost of the LP solution (which is in turn within
a factor (1 + ε) of the fractional optimum).
Let C1 , C2 , ..., C2J be all possible configurations sorted by decreasing cost, i.e., cost(C1 ) ≥ . . . ≥
cost(C2J ). To simplify notation, in this section we let J denote the set of jobs that can be processed
on machine i⋆ (i.e., Ji⋆ ).
Recall that the solution y ⋆ to the Configuration-LP gives us an input distribution
P in on configuJ
⋆
in
2
rations assigned to machine i , i.e., it gives us a vector y ∈ [0, 1] such that i yi = 1. With
this notation, we can write the cost of the Configuration-LP on machine i⋆ as
X
yiin cost(Ci ).
i

In order to compare this expression with the expected cost of our algorithm on machine i⋆ ,
we observe that our rounding algorithm also givesPa distribution on configurations. We denote
J
this output distribution by y out ∈ [0, 1]2 (where i yiout = 1). Hence, the expected cost of our
algorithm on machine i⋆ is
X
yiout cost(Ci ).
i

The result of this section that implies the approximation guarantee of Theorem 1.1 can now be
stated as follows.
Theorem 4.1. We have

√
P out
yi cost(Ci )
1+ 2
i
P in
.
≤
2
i yi cost(Ci )

Our strategy for bounding this ratio is, broadly, to work on this pair of distributions by transforming it to another pair of distributions of special form, whose ratio we will be able to bound.
We transform the pair in such a way that the ratio can only increase. In other words, we prove
that no pair of distributions has a worse ratio than a certain worst-case kind of pair, and we bound
the ratio in that worst case.
After these transformations, our pair of distributions may no longer correspond to the original
scheduling problem instance, so it will be convenient for us to work with a more abstract notion
that we define now.

4.1

Compatible Function Pairs

P
J
Given a distribution y ∈ [0, 1]2 with i yi = 1, we can build a corresponding function f from
[0, 1) to multisets of positive numbers as follows: define f (x) for x ∈ [0, y1 ) to be the multiset of
processing times of jobs in C1 , f (x) for x ∈ [y1 , y1 + y2 ) to be the multiset of processing times of
jobs in C2 , and so on.7 If we do this for both y out – obtaining a function f – and y in – obtaining a
function g (see Figure 1 for an illustration of f and g), we will have produced a function pair :
7
Recall that C1 , C2 , ... are sorted by non-increasing cost. Thus f can be thought of as a quantile function (inverse
cumulative distribution function) of the distribution y, except in reverse order (i.e., f (1 − x) is a quantile function).

7

Definition 4.2. A function pair is a pair (f, g) of stepwise-constant functions from the interval
[0, 1) to multisets of positive numbers. We will call these multisets patterns and the numbers they
contain elements (or processing times).
Notation.

If f is such a function, define:

• f1 : [0, 1) → R+ as the maximum element: f1 (x) = max f (x) (set 0 if f (x) = ∅),
• sizef : [0, 1) → R+ as sizef (x) = size(f (x)), where
size(f (x)) =

X

p,

p∈f (x)

• fr as the total size of the multiset after the removal of the maximum: fr (x) = sizef (x)−f1 (x),
R1
• cost(f ) = 0 cost(f (x)) dx as the fractional (expected) cost, where


X
X
q
cost(f (x)) =
p·
p∈f (x)

q∈f (x),qp

for an arbitrary linear order  on f (x).8

Function pairs we work with will have special properties that follow from the algorithm. We
argue about them in Fact 4.4. One such property comes from our algorithm preserving the marginal
probabilities of jobs:
Definition 4.3. We say that a function pair (f, g) is a compatible function pair (CFP) if the
fractional number of occurences of any element is the same in f and in g.9
Fact 4.4. Let (f, g) be a function pair obtained from (y out , y in ) as described above. Then:
• (f, g) is a CFP.
P
P
• cost(f ) = i yiout cost(Ci ) and cost(g) = i yiin cost(Ci ).

• f has the following bucket structure: for any two patterns P and Q in the image of f and
for any i, the i-th largest element of P is no smaller than the (i + 1)-th largest element of Q.
Proof. That (f, g) is a CFP follows because our algorithm satisfies the marginals of the involved
jobs. Namely, we know that
job j ∈ J , both distributions y in and y out have the machine i⋆
P for each
⋆
process a fraction xi⋆ j = C∋j yi⋆ C of this job (where y ⋆ is the global Configuration-LP solution).
For any p > 0, summing this up over all jobs j ∈ J with processing time pj = p gives the
compatibility condition.
The equalities of costs are clear from the definition of cost(f ) and cost(g).
For the bucket structure of f , recall the algorithm: a matching is found between jobs and
buckets, in which each bucket is matched with a job (except potentially for the last bucket of each
machine). For any pattern P in the image of f and for any i, the i-th processing time in P is
drawn from the i-th bucket that was constructed by our algorithm. Moreover, all processing times
in the i-th bucket are no smaller than those in the (i + 1)-th bucket, because the algorithm orders
jobs non-increasingly by processing times. (See Figure 1 for an illustration of this process and of a
function f satisfying this bucket structure.)
8

This expression does not depend on , since the Smith ratios are uniform, and it is equal to the cost of a
configuration giving rise to f (x).
R1
R1
9
Formally, for each p > 0 we have: 0 multiplicity of p in f (x) dx = 0 multiplicity of p in g(x) dx.

8

This was the last point in the analysis where we reasoned about how the algorithm rounds the
LP solution. From now on, we will think about elements, patterns and CFPs rather than jobs and
configurations.
√
)
1+ 2
≤
To prove Theorem 4.1, we need to show that cost(f
2 . As indicated above, we will do this
cost(g)
′

cost(f )
)
by proving that there is another CFP (f ′ , g′ ) with special properties and such that cost(f
cost(g) ≤ cost(g ′ ) .
We will actually construct a series of such CFPs in a series of lemmas, obtaining more and more
desirable properties, until we can bound the ratio. Our final objective is a CFP like the pair (f ′ , g′ )
depicted in Figure 3.

4.2

The Worst-Case Output

As a first step, we look at how costly an output distribution of our algorithm can be (while still
satisfying the aforementioned bucket structure and the marginal probabilities, i.e., the compatibility
condition). Intuitively, the maximum-cost f is going to maximize the variance of the total processing
time, which means that larger-size patterns should select larger processing times from each bucket.
(See Figure 1 for an illustration and the proof of Lemma 4.5 for details.) From this, we extract
that the largest processing time in a pattern (the function f1 ) should be non-increasing, and this
should also hold for the second-largest processing time, the third-largest, and so on. This implies
the following properties:
Lemma 4.5. If (f, g) is a CFP where f has the bucket structure described in Fact 4.4, then there
cost(f ′ )
)
′
′
exists another CFP (f ′ , g) such that cost(f
cost(g) ≤ cost(g) and the functions f1 and fr are non-increasing
and size(f ′ (1)) ≥ fr′ (0).
The proof is a simple swapping argument.
Proof. For i = 1, 2, ..., let fi (x) always denote the i-th largest element of f (x). As suggested above,
we will make sure that for each i, the function fi is non-increasing.
Namely, we repeat the following procedure: as long as there exist x, y and i such that
size(f (x)) > size(f (y)) but fi (x) < fi (y), swap the i-th largest elements in f (x) and f (y).10
Once this is no longer possible, we finish by “sorting” f so as to make sizef non-increasing.
Let us verify that once this routine finishes, yielding the function f ′ , we have the desired
properties:
• The function f1′ is non-increasing.
• The same holds for the function fr′ , since fr′ = f2′ + f3′ + ... and each fi′ is non-increasing.
′ (y) for all i, x
• The procedure maintains the bucket structure, which implies that fi′ (x) ≥ fi+1
and y. Thus
f ′ (1) = f1′ (1) + f2′ (1) + ... ≥ f2′ (0) + f3′ (0) + ... = fr′ (0).

• It remains to show that cost(f ′ ) ≥ cost(f ). Without loss of generality, assume there was only
a single swap (as the sorting step is insignificant for the cost). For computing the cost of the
involved patterns, we will think that the involved elements went last (since the order does
10

Formally, choose τ > 0 such that f is constant on [x, x + τ ) and on [y, y + τ ) and perform the swap in these
patterns.

9

not matter); let Rx = size(f (x)) − fi (x) and Ry = size(f (y)) − fi (y) be the total sizes of the
elements not involved. Then Rx ≥ Ry and
∆ cost(f (x)) = fi (y) (Rx + fi (y)) − fi (x) (Rx + fi (x))
= (fi (y) − fi (x)) Rx + fi (y)2 − fi (x)2 ,

∆ cost(f (y)) = fi (x) (Ry + fi (x)) − fi (y) (Ry + fi (y))
= (fi (x) − fi (y)) Ry + fi (x)2 − fi (y)2 ,

thus
∆ cost(f (x)) + ∆ cost(f (y)) = (fi (y) − fi (x)) (Rx − Ry ) > 0.

4.3

Liquification

One of the most important operations we will employ is called liquification. It is the process of
replacing an element (processing time) with many tiny elements of the same total size. These new
elements will all have a size of ε and will be called liquid elements. Elements of size larger than
ε are called solid. One should think that ε is arbitrarily small, much smaller than any pj ; we will
usually work in the limit ε → 0.
The intuition behind applying this process to our pair is that in the ideal worst-case setting
which we are moving towards, there are only elements of two sizes: large and infinitesimally small.
We will keep a certain subset of the elements intact (to play the role of large elements), and liquify
the rest in Lemma 4.7.
Our main claim of this section is that replacing an element with smaller ones of the same total
size (in both f and g) can only increase the ratio of costs. Thus we are free to liquify elements in
our analysis as long as we make sure to liquify the same amount of every element in both f and g
(f and g remain compatible).
Fact 4.6. Let (f, g) be a CFP and p, p1 , p2 > 0 with p = p1 + p2 . Suppose (f ′ , g′ ) is a CFP obtained
from (f, g) by replacing p by p1 and p2 in subsets of patterns in f and g of equal measures.11 Then
cost(f ′ )
cost(f )
cost(g) ≤ cost(g ′ ) .
Proof. Consider a pattern P in which p was replaced. We calculate the change in cost ∆ :=
cost(P \ {p} ∪ {p1 , p2 }) − cost(P ). As the order does not matter, the cost can be analyzed with p
(or p1 , p2 ) being first, so
∆ = (p21 + p2 (p1 + p2 )) − p2 = (p21 + p1 p2 + p22 ) − (p1 + p2 )2 = −p1 p2 ≤ 0
and it does not depend on the other elements in P . Thus, if we make the replacement in a fraction
τ of patterns, then we have
cost(f ) + τ ∆
cost(f )
cost(f ′ )
=
≥
′
cost(g )
cost(g) + τ ∆
cost(g)
since

cost(f )
cost(g)

≥ 1 to begin with (otherwise we are done) and ∆ ≤ 0.

By corollary, we can also replace an element of size p with p/ε liquid elements (of size ε each).
11
Formally, suppose If , Ig ⊆ [0, 1) are finite unions of disjoint intervals of equal total length such that all patterns
f (x) and g(y) for x ∈ If , y ∈ Ig contain p; in all these patterns, remove p and add p1 , p2 .

10

f1 (x) + fr (0)
fr (0)
size(f (x))

⇒

f1 (x)
size(f (x)) − fr (0)

m

0

1

0

m

1

Figure 2: The main step in the proof of Lemma 4.7. The left picture shows f after the liquification
of all elements except one largest element (f1 ) for x ∈ [0, m). The right picture shows
f after the movement of liquid elements between the striped regions. In both pictures,
the light-gray areas contain single large elements, and the dark-gray areas are liquid
elements. Note that there are two pairs of parallel lines in the pictures; the vertical
distance between each pair is fr (0). The threshold m is defined so that the striped
regions have equal areas (thus fr′ is made constant by the movement of liquid elements)
and so that moving the liquid elements can only increase the cost. The height of the
upper striped area is f1 (x) + fr (0) − size(f (x)) = fr (0) − fr (x) for x ∈ [0, m) and the
height of the lower striped area is size(f (x)) − fr (0) for x ∈ [m, 1). All functions are
stepwise-constant, but drawn here using straight downward lines for simplicity; also,
the rightmost dark-gray part will “fall down” (forming a (1 − m) × fr (0) rectangle).

4.4

The Main Transformation

In this section we describe the central transformation in our analysis. It uses liquification and
rearranges elements in f and g so as to obtain two properties: that fr is constant and that f1 = g1 .
(The process is explained in Figure 2, and a resulting CFP is shown in the upper part of Figure 3.)
This greatly simplifies the setting and brings us quite close to our ideal CFP (depicted in the lower
part of Figure 3).
Lemma 4.7. If (f, g) is a CFP with f1 and fr non-increasing and size(f (1)) ≥ fr (0), then there
)
cost(f ′ )
exists another CFP (f ′ , g′ ) with cost(f
cost(g) ≤ cost(g ′ ) such that:
(a) fr′ is constant.
(b) f1′ = g1′ and it is non-increasing.
(c) There exists m ∈ [0, 1] such that:
• for x ∈ [0, m), f ′ (x) has liquid elements and exactly one solid element,
• for x ∈ [m, 1), f ′ (x) has only liquid elements.

Proof. We begin with an overview of the proof. See also Figure 2.
Our procedure to obtain such a CFP has three stages:
1. We liquify all elements except for the largest element of every pattern f (x) for x ∈ [0, m), for
a certain threshold m; at this point, fr (x) becomes essentially the size of liquid elements in
f (x) for x ∈ [0, 1) (since no pattern contains two solid elements).
2. We move liquid elements in f from right to left, i.e., from f (y) for y ∈ [m, 1) to f (x) for
x ∈ [0, m) (which only increases the cost of f ), so as to make fr constant.
11

3. We rearrange elements in g so as to satisfy the condition f1′ = g1′ .
Now let us proceed to the details. First, we explain how to choose the threshold m. It is defined
so as to ensure that after the liquification, patterns in f have liquid elements of total size fr (0)
on average. Thus we can make all fr (x) equal to fr (0). More importantly, we can do this by
only moving the liquid elements “higher”, so that the cost of f only goes up. (See Figure 2 for an
illustration of this move.)
More precisely, m ∈ [0, 1] is chosen so that
Z

0

m

fr (0) − fr (x) dx =

Z

1

m

size(f (x)) − fr (0) dx

(1)

Rm
R1
(which implies fr (0) = 0 fr (x) dx + m size(f (x)) dx: the right-hand expression is the size of
elements which will be liquified next). Such an m is guaranteed to exist by nonnegativity of
the functions under both integrals in (1), which follows from our assumptions on f (we have
size(f (x)) ≥ size(f (1)) ≥ fr (0), because sizef = f1 + fr is non-increasing).
Now we can perform the sequence of steps:
1. The liquification: for each element p > 0 which appears in a pattern f (x) \ {f1 (x)} for
x ∈ [0, m) or in a pattern f (x) for x ∈ [m, 1), we liquify all its such occurences, as well as
their counterparts in g.12 We have a bound on the ratio of costs by Fact 4.6, and f1 remains
non-increasing.
2. Rearranging liquid elements in f : while there exists x ∈ [0, m) with fr (x) < fr (0), find
y ∈ [m, 1) with fr (y) > fr (0) and move a liquid element from f (y) to f (x).13 (Since we
want to make fr constant and equal to fr (0), we move elements from where fr is too large
to where it is too small. Note that since we liquified all elements in f (x) for x ∈ [m, 1), now
sizef is almost equal to fr on [m, 1).) Once this process finishes, fr will be constant by the
definition of m.14 (See the right side of Figure 2.) Note that sizef was non-increasing at the
beginning of this step, and so we are always moving elements from patterns of smaller total
size to patterns of larger total size – this can only increase the cost of f and thus the ratio of
costs increases. This step preserves f1 .
3. Rearranging elements in g: at this point, since f and g are compatible, g only has solid jobs
that appear as f1 (x) for x ∈ [0, m), but they might be arranged differently in g than in f . We
want them to have the same arrangement (i.e., f1′ = g1′ ) so that we can compare f to g more
easily. As a first step, we make sure that every pattern in g has at most one solid element. To
this end, while there exists x ∈ [0, 1) such that g(x) contains two or more solid elements, let
p > 0 be one of them, and find y ∈ [0, 1) such that g(y) contains only liquid elements15 . Now
there are two cases: if size(g(y)) ≥ p, then we move p to g(y) and move liquid elements of the
same total size back to g(x). This preserves cost(g) (think that these elements went first in
12

Formally, let If = {x ∈ [0, m) : p ∈ f (x) \ {f1 (x)}} ∪ {x ∈ [m, 1) : p ∈ f (x)} and Ig = {y ∈ [0, 1) : p ∈ g(y)}; by
compatibility of f and g, the measure of Ig is no less than that of If . We liquify p in If and in a subset of Ig of the
right measure. (If there were patterns where p appeared multiple times, we repeat.)
13
Formally, let τ > 0 be such that fr (x′ ) < fr (0) for x′ ∈ [x, x + τ ) and x + τ ≤ m and fr (y ′ ) > fr (0) for
′
y ∈ [y, y + τ ). Move the liquid elements between these patterns f (y ′ ) and f (x′ ).
14
Since we operate in the limit ε → 0, we ignore issues such as fr being ±ε off.
15
Such a y exists because f and g are compatible: the total measure of patterns with solid elements in f is m and
these patterns contain only one solid element each, so g must have patterns with no solid elements.

12

the linear orders on both g(x) and g(y)). On the other hand, if size(g(y)) < p, then we move
p to g(y) and move all liquid elements from g(y) to g(x). This even decreases cost(g).16
At this point, f and g have the same solid elements, each of which appears as the only solid
element in patterns containing it in both f and g. Thus we can now sort g so that for each
solid element p > 0, it appears in the same positions in f and in g. This operation preserves
cost(g), and thus the entire third step does not decrease the ratio of costs.

4.5

The Final Form

In our last transformation, we will guarantee that in g, each large element is the only member
of a pattern which contains it. (Intuitively, we do this because such CFPs are the ones which
maximize the ratio of costs.) Namely, we prove Lemma 4.8, a strengthened version of Lemma 4.7;
note that condition (c’) below is stronger than condition (c) of Lemma 4.7 (there, g′ could have
had patterns with both liquid and solid elements), and that condition (d) is new. Figure 3 shows
the difference between CFPs postulated by Lemmas 4.7 and 4.8.
Lemma 4.8. Let (f, g) be as postulated in Lemma 4.7. Then there exists another CFP (f ′ , g′ ) such
that:
(a) fr′ is constant.
(b) f1′ = g1′ .
(c’) There exists t ∈ [0, 1] such that:
• for x ∈ [0, t), f ′ (x) has liquid elements and exactly one solid element,

• for x ∈ [t, 1), f ′ (x) has only liquid elements,

• for x ∈ [0, t), g ′ (x) has exactly one solid element (and no liquid ones),
• for x ∈ [t, 1), g ′ (x) has only liquid elements.

(d) The function sizeg′ is constant on [t, 1) (i.e., the liquid part of g is uniform).
Moreover,



cost(f )
cost(f ′ )
≥
min
2,
.
cost(g ′ )
cost(g)

Proof. Let us begin by giving a proof outline; see also Figure 3 for an illustration.
• Our primary objective is to make g1 equal to sizeg on [0, t) (where t is to be determined).
To this end, we increase the sizes of the solid elements in g(x) for x ∈ [0, t) and at the same
time decrease the total sizes of liquid elements for these g(x) (which keeps sizeg unchanged).
To offset this change, we decrease the sizes of solid elements in g(y) for y ∈ [t, m) (and also
increase the total sizes of liquid elements there). We also modify the sizes of solid elements
in f so as to keep f and g compatible and preserve the properties (a)-(b).
16
Formally, select τ > 0 so that g is constant on [x, x + τ ) and on [y, y + τ ); for x′ ∈ [x, x + τ ), replace g(x′ ) with
g(x′ ) \ {p} ∪ g(y), and for y ′ ∈ [y, y + τ ), replace g(y ′ ) with {p}. The cost of g then decreases by τ (size(g(x)) − p)(p −
size(g(y))) > 0.

13

g

f
fr

f1

g1 = f1

t

0

m

1

m

⇓

f′

1
g′

f1

0

t

0

g1 = f1

t

m

1

t

0

m

1

Figure 3: An example of two CFPs: (f, g) is produced by Lemma 4.7, whereas (f ′ , g′ ) is produced
by Lemma 4.8. In this picture, the height of the plot corresponds to size(f (x)) for
each x, while the shaded and wavy parts correspond to the contributions of f1 and fr
to sizef ; similarly for g. The wavy parts are liquid. In Lemma 4.8 we want to make
f1 = g1 equal to sizeg on an interval [0, t), so we increase sizes of solid elements in g
on that interval, while decreasing those on the interval [t, m). The striped regions in
the pictures of g correspond to these changes. (We repeat the same changes in f , and
we also move liquid elements in g to keep sizeg unchanged.) The threshold t ∈ [0, m] is
chosen so that g1 becomes equal to sizeg on [0, t) while the solid elements on [t, m) are
eradicated (i.e., so that the areas of the striped regions in g are equal).
• The threshold t is defined so that after we finish this process, the solid elements in g(x)
for x ∈ [0, t) will have filled out the entire patterns g(x), and the solid elements in g(y) for
y ∈ [t, m) will have disappeared.
• Our main technical claim is that this process does not invalidate the ratio of costs.
• Finally, we can easily ensure condition (d) by levelling g on [t, 1), which only decreases its
cost.
Now we proceed to the details. First we define the threshold t ∈ [0, m] as a solution to the equation
Z

t

gr (x) dx =
0

Z

t

14

m

g1 (x) dx,

which exists because the functions under both integrals are nonnegative. The left-hand side will
be the total increase in sizes of solid elements in g(x) for x ∈ [0, t) and the right-hand side will
be the total decrease in sizes of solid elements in g(y) for y ∈ [t, m) (these elements will disappear
completely).
Now we will carry out the process that we have announced in the outline. Namely, while there
exists x ∈ [0, t) with gr (x) > 0, do the following:
• find y ∈ [t, m) with g1 (y) > ε (i.e., g(y) where the solid element has not been eradicated yet),
• increase the size of the solid element in g(x) by ε,
• do the same in f ,
• decrease the size of the solid element in g(y) by ε,
• do the same in f ,
• move one liquid element (of size ε) from g(x) to g(y).
Formally, as usual, we find τ > 0 such that f and g are constant on [x, x + τ ) and on [y, y + τ )
and we do this in all of these patterns.
Note that the following invariants are satisfied after each iteration:
• f1 = g1 ,
• fr does not change,
• sizeg does not change,
Rm
• 0 g1 (x) dx does not change,

• g1 can only increase on [0, t) and it can only decrease on [t, m),
• f1 (x) ≥ f1 (y) for all x ∈ [0, t) and y ∈ [t, m).17
By the definition of t, when this process ends, the patterns g(x) for x ∈ [0, t) contain only a
single solid element, while g(x) for x ∈ [t, m) (thus also for x ∈ [t, 1)) contain no solid elements.
Since f1 = g1 , the patterns f (x) also have only liquid elements for x ∈ [t, 1). Thus properties (a),
(b) and (c’) are satisfied. We reason about the ratio of costs in the following two technical claims:
Claim 1. In a single iteration, cost(f ) increases by 2α and cost(g) increases by α, for some α ≥ 0.
Proof. The patterns have changed so that:
• f (x) had f1 (x) increased by ε,
• f (y) had f1 (y) decreased by ε,
• g(x) had g1 (x) increased by ε and one liquid element removed,
• g(y) had g1 (y) decreased by ε and one liquid element added.
17
This is because f1 = g1 was initially non-increasing and since then it has increased on [0, t) and decreased on
[t, m).

15

Since the order of elements does not matter, in computing cost(f ) we think that the solid element
goes last in the linear order:
∆ cost(f (x)) = (f1 (x) + ε)(size(f (x)) + ε) − f1 (x) size(f (x)) = ε (size(f (x)) + f1 (x) + ε) ,

∆ cost(f (y)) = (f1 (y) − ε)(size(f (y)) − ε) − f1 (y) size(f (y)) = ε (− size(f (y)) − f1 (y) + ε) ,
∆ cost(f (x)) + ∆ cost(f (y)) = ε (size(f (x)) − size(f (y)) + f1 (x) − f1 (y) + 2ε)
= 2ε (f1 (x) − f1 (y) + ε) ,

where in the last line we used that size(f (x)) − size(f (y)) = f1 (x) + fr (x) − f1 (y) − fr (y) =
f1 (x) − f1 (y) since fr is constant.
In computing cost(g), we think that the solid element and the one liquid element which was
added or removed go first (and other elements are unaffected since sizeg is preserved):
∆ cost(g(x)) = (g1 (x) + ε)2 − (g1 (x)2 + ε(g1 (x) + ε)) = εg1 (x),
∆ cost(g(y)) = ((g1 (y) − ε)2 + εg1 (y)) − g1 (y)2 .

Adding up we have:
∆ cost(g(x)) + ∆ cost(g(y)) = ε (g1 (x) − g1 (y) + ε) = ε (f1 (x) − f1 (y) + ε) ,
where we used that f1 = g1 . Thus we have that
∆ cost(f (x)) + ∆ cost(f (y)) = 2 [∆ cost(g(x)) + ∆ cost(g(y))]
and we get the statement by setting
α = τ (∆ cost(g(x)) + ∆ cost(g(y))) = τ ε (f1 (x) − f1 (y) + ε) ≥ 0
(recall that τ is the fraction of patterns where we increase g1 ; nonnegativity follows by the last
invariant above).
Claim 2. Let (f ′ , g′ ) be the CFP obtained at this point and (f, g) be the original CFP. Then


cost(f ′ )
cost(f )
≥ min 2,
.
cost(g ′ )
cost(g)
Proof. By Claim 1, we have cost(f ′ ) = cost(f ) + 2β and cost(g ′ ) = cost(g) + β for some β ≥ 0
(which is the sum of α’s from Claim 1). Now there are two cases:
• if

cost(f )
cost(g)

≤ 2, then

cost(f )+2β
cost(g)+β

≥

• if

cost(f )
cost(g)

≥ 2, then

cost(f )+2β
cost(g)+β

≥ 2 (even though the ratio decreases, it stays above 2).

cost(f )
cost(g) ,

Finally, as the last step, we equalize the total sizes of liquid elements in g(x) for x ∈ [t, 1) (by
moving liquid elements from larger patterns to smaller patterns, until all are equal), thus satisfying
property (d). Clearly, this can only decrease the cost of g (by minimizing the variance of sizeg on
the interval [t, 1)), so the ratio increases and Lemma 4.8 follows.

16

Note that Lemma 4.8 does not guarantee that the ratio of costs increases; we only claim that
it either increases, or it is now more than 2. However, we will shortly show in Lemma 4.9 that the
ratio is actually much below 2, so the latter is in fact impossible.
Now that we have our ideal CFP, we can finally bound its cost ratio.
Lemma 4.9. Given a CFP (f, g) as postulated in Lemma 4.8 (see the lower part of Figure 3), we
have
√
cost(f )
1+ 2
≤
.
cost(g)
2
The proof proceeds in two simple steps: first, we argue that we can assume without loss of generality
that there is only a single large element (i.e., f1 = g1 is constant on [0, t)). Then, for such pairs of
functions, the ratio is simply a real function of three variables whose maximum is easy to compute.
Proof. As a first step, we assume without loss of generality that there is only a single large element
(i.e., f1 = g1 is constant on [0, t)). This is due to the fact that both f and g can be written as a
weighted average of functions
with a single large element. Formally, let ℓ1 , ℓ2 , ... be the step lengths
P
of f1 on [0, t), so that i ℓi = t and f1 is constant on [0, ℓ1 ), on [ℓ1 , ℓ1 + ℓ2 ) and so on. Define f i
to be f with the whole f1 on [0, t) replaced by the i-th step of f1 , i.e.,
(
f (ℓ1 + ... + ℓi−1 ) for x ∈ [0, t),
f i (x) =
f (x)
for x ∈ [t, 1).
Define g i similarly. Then
cost(f ) =

X
i

=

X ℓi
i

=
and similarly cost(g) =

t

X ℓi
i

P

ℓi cost(f (ℓ1 + ... + ℓi−1 )) + (1 − t) · cost(f (1))

ℓi
i t

t

[t · cost(f (ℓ1 + ... + ℓi−1 )) + (1 − t) · cost(f (1))]
cost(f i )

cost(gi ). Thus, if we have

cost(f i )
cost(g i )

≤

√
1+ 2
2

for each i, then

√
P ℓi
P ℓi 1+√2
i
cost(g i )
cost(f )
1+ 2
i t cost(f )
i t
2
= P ℓ
.
≤
=
P ℓi
i
i
i
cost(g)
2
i t cost(g )
i t cost(g )

So we assume that f1 is constant on [0, t) (i.e., the shaded areas in Figure 3 are rectangles). Let
γ = f1 (0) be the large element and λ be the total mass of liquid elements (the same in f as in g),
i.e., λ = f (1) = (1 − t)g(1). In the limit ε → 0 we have




R
R
2 + λ (γ + x) dx + (1 − t) λ xdx
2 + γλ + λ2 + (1 − t) λ2
2
t
γ
t
γ
tγ 2 + tγλ + λ2
2
2
0
0
cost(f )
=
=
=
R g(1)
2
λ
λ2
cost(g)
( 1−t
)
tγ 2 + 2(1−t)
tγ 2 + (1 − t) 0 x dx
2
tγ + (1 − t) 2
√

and we need to prove that this expression is at most 1+2 2 for all t ∈ [0, 1), γ ≥ 0 and λ ≥ 0. So
we want to show
√ 

1+ 2
λ2
λ2
2
2
≤
tγ + tγλ +
tγ +
,
2
2
2(1 − t)
17

that is,

!
√
√
1
2−1 2
1+ 2
− λ · tγ +
−
tγ ≥ 0.
4(1 − t) 2
2

λ2
√

1+ 2
Note that 4(1−t)
− 12 > 0 for t ∈ [0, 1), so this is a quadratic polynomial in λ whose minimum value
(over λ ∈ R) is
!
√
√
t2 γ 2
t
2−1 2
2−1
2
 = tγ
tγ −  √
− √
1+ 2
2
2
−2
4 1+ 2 − 1
4(1−t)

1−t

2

and we should prove that this is nonnegative. If t= 0√or γ =
 0, then this is clearly true; otherwise
1−t 1+ 2
we multiply both sides of the inequality by tγ 2
1−t − 2 (a positive number) and after some
calculations we are left with showing
√
√

3−2 2
2
≥0
t +
2−2 t+
2
but this is again a quadratic polynomial, whose minimum is 0.

Proof of Theorem 4.1. Now it is straightforward to see that
√



 P out
cost(Ci )
cost(f ′ )
cost(f )
1+ 2
i yi
P
≥
≥ min 2,
= min 2,
in
2
cost(g′ )
cost(g)
i yi cost(Ci )

where (f, g) is produced from (y out , y in ) as in Fact 4.4 and (f ′ , g′ ) is produced from (f, g) by
applying
Lemmas 4.5,√4.7 and
4.8; the first inequality is by Lemma 4.9. It follows that either
P out
√
y
cost(Ci )
1+ 2
1+ 2
Pi iin
.
≥
2
(false)
or
≥
2
2
y cost(C )
i

i

i

On the other hand, to conclude the proof of Theorem 1.1, we have the following lemma regarding
the tightness of our analysis of Algorithm 1:
P
Lemma 4.10. For any δ > 0, there is an instance I of R|| pj Cj whose optimal value is c, and
an optimal Configuration-LP solution whose objective
value is also c, such that the rounded solution
√
1+ 2
returned by Algorithm 1 has cost at least ( 2 − δ)c.
Proof. The intuitive explanation is that the bound in Lemma 4.9 is tight and
√ thus there exists a
1+ 2
CFP in the final form (as postulated by Lemma 4.8)
P with ratio exactly 2 . Furthermore, this
CFP indeed almost corresponds to an instance of R|| pj Cj (except for the fact that the parameters
which maximize the ratio are irrational). We make this intuition formal in the following.
Let
2
tγ 2 + tγλ + λ2
h(t, γ, λ) =
λ2
tγ 2 + 2(1−t)
be the function specifying the ratio of CFPs in the final form. In Lemma 4.9, we proved that
h(t, γ, λ) ≤ 12 + √12 for all t, γ, λ ∈ [0, 1]. To begin, let us fix the following maximizer (t⋆ , λ⋆ , γ ⋆ ) of
h: t⋆ = 1 −

√1 ,
2

γ⋆ =

1
2

and λ⋆ =

√

2−1
2 ;

we have h(t⋆ , λ⋆ , γ ⋆ ) =

√1
2

+ 12 .

Let us choose a small rational η. Next,
let us fix rationals t̃ ∈ [t⋆ − η, t⋆ ], λ̃ ∈ [λ⋆ − η, λ⋆ ] and
√
2
1+
γ̃ ∈ [γ ⋆ , γ ⋆ + η] such that h(t̃, γ̃, λ̃) ≥ 2 − η. Then, there exist positive integers k, T and Λ
such that T = t̃k and Λ = k λ̃. Finally, select a small rational ǫ ≤ η such that ε =

integer k1 > 0, and ε =

λ̃
k2 ,

for some integer k2 > 0.
18

λ̃
,
k1 (1−t̃)

for some

P
Next, we create an instance Iε of R|| pj Cj which consists of k machines, a set T of T jobs of
size γ̃ each, and a set L of Λ/ε jobs of size ε each; any job can be assigned to any machine. An
optimal solution to this instance will assign the jobs from T alone on T machines, and distribute
the jobs from L evenly on the rest of the machines (i.e., these machines will all receive λ̃ε jobs of
size ε each). The fact that this is an optimal solution follows in a straightforward manner from the
following two observations:
• A solution which assigns a job from L on the same machine as a job from T is sub-optimal:
indeed, the average makespan is less than γ̃ (in fact, it is exactly t̃γ̃ + λ̃, which is at most γ̃,
due to the fact that t⋆ γ ⋆ + λ⋆ < γ ⋆ and due to the intervals which we choose t̃, γ̃ and λ̃ from),
which implies that we can always reassign such a job to a machine with smaller makespan,
thus decreasing the solution cost.
• Similarly, in any optimal solution, jobs from T are not assigned on the same machine.
Now, consider the Configuration-LP solution yε which assigns to every machine a configuration
which consists of a single job from T (i.e., of cost γ̃ 2 ) with probability t̃, and a configuration
P
P
λ̃2
λ̃
2
which consists of (1−λ̃t̃)ε jobs from L (i.e., of cost 1≤i≤ λ̃
1≤j<i ε = 2(1−t̃)2 + 2(1−t̃) ε) with
(1−t̃)ε

probability 1− t̃; clearly, the cost of this LP solution is equal to that of any optimal integral solution
(in fact, the LP solution is a convex combination of all integral optimal solutions). Furthermore,
this LP solution is optimal (one can see this by applying the reasoning we used for the integral
optimum to all the configurations in the support of a fractional solution).
Algorithm 1 will assign to any machine a configuration which consists of a single job from T and
P
P
2
λ̃/ε jobs from L (i.e., of cost γ̃(γ̃ + λ̃) + 1≤i≤ λ̃ 1≤j<i ε2 = γ̃(γ̃ + λ̃) + λ̃2 + λ̃2 ε) with probability
ε
P
P
2
t̃, and a configuration which consists of λ̃/ε jobs from L (i.e., of cost 1≤i≤ λ̃ 1≤j<i ε2 = λ̃2 + λ̃2 ε)
ε

with probability 1− t̃. To see this, first observe that every machine has a total fractional assignment
of jobs from T equal to t̃, and a total fractional assignment of jobs from L equal to λ̃ε . Therefore,
the first bucket created by Algorithm 1 for any machine will contain a t̃-fraction of T -jobs and an
(1 − t̃)-fraction of L-jobs, and the rest of the buckets will be filled up with L-jobs (since λ̃ε is an
integer, the last bucket will be filled up to a t̃-fraction). This implies that, in a worst-case output
distribution, with probability t̃ any machine receives a T -job and L-jobs of total size λ̃, and with
probability (1 − t̃) it receives L-jobs of total size λ̃.
Now, the ratio of the expected cost of the returned solution to the LP cost, for any machine, is
then
t̃γ̃ 2 + t̃γ̃ λ̃ +
t̃γ̃ 2 +

λ̃2
2

λ̃2
2(1−t̃)

+ λ̃2 ε

+ λ̃2 ε

≥

t̃γ̃ 2 + t̃γ̃ λ̃ +
t̃γ̃ 2 +

λ̃2
2(1−t̃)

λ̃2
2

+ λ̃ 2ε

t̃γ̃ 2 +
= h(t̃, γ̃, λ̃)

t̃γ̃ 2 +

λ̃2
2(1−t̃)

λ̃2
2(1−t̃)

+ λ̃2 ε

√

which is at least 1+2 2 − δ if we pick ε and η small enough; since the cost of the LP solution is equal
to that of any optimal integral solution, the claim follows.
It is interesting to note that, given the instance and LP solution from the proof of Lemma 4.10,
any random assignment produced by Algorithm 1 will assign the same amount of small jobs to all the
machines, while it will assign a large job to a t̃-fraction of the machines. Therefore derandomizing
Algorithm 1 by picking
the best possible matching (instead of picking one at random) will not
√
1+ 2
improve upon the 2 ratio.
Theorem 4.1 and Lemma 4.10 together imply Theorem 1.1.
19

J12
M1

M2

J13

J24

J23

J14

M4

M3
J34

13
Figure 4: The 12
-integrality gap instance. In this picture, black circles correspond to machines,
gray boxes correspond to jobs of size 3, and white boxes correspond to jobs of size 1.
An edge between a circle and a box means that the corresponding job can be assigned
to the corresponding machine.

5

Integrality Gap Lower Bound

First of all, observe
Pthat Theorem 1.1, apart from establishing the existence of a 1.21-approximation
algorithm for R|| j pj Cj , also implies an upper bound on the integrality gap of its ConfigurationLP. Hence, we accompany
P our main result with a lower bound on the integrality gap of the
Configuration-LP for R|| j pj Cj :
P
Theorem 1.2. The integrality gap of the Configuration-LP for R|| pj Cj is at least 1.08.

Proof. Consider the following instance on 4 machines M1 , M2 , M3 , M4 : for every pair {Mi , Mj } of
machines there is one job Jij which can be processed only on these two machines. Jobs J12 and
J34 are large: they have weight and size 3, while the other four jobs are small and have weight and
size 1. (See Figure 4 for an illustration.)
First we show that any integral schedule has cost at least 26. Without loss of generality, the
large job J12 is assigned to machine M1 and the other large job J34 is assigned to machine M3 .
The small job J13 must also be assigned to one of them, say to M1 . This costs 9 + 9 + 4 = 22. The
remaining three small jobs J12 , J14 and J24 cannot all be assigned to distinct machines with zero
makespan (since only M2 and M4 are such), so they will incur at least 1 + 1 + 2 = 4 units of cost.
On the other hand, the Configuration-LP has a solution of cost 24. Namely, it can assign to
each machine Mi two configurations, each with fractional value 12 : the singleton large job that can
be processed on that machine, or the two small jobs that can be processed on that machine. Then
each job is processed with fractional value 12 by each of the two machines that can process it. The
13
cost is 4 · ( 21 · 9 + 21 · (1 + 2)) = 24. Thus the integrality gap is at least 26
24 = 12 > 1.08.

20

References
[BCS74]

J. Bruno, E.G. Coffman, Jr., and R. Sethi. Scheduling independent tasks to reduce
mean finishing time. Comm. ACM, 17:382–387, 1974.

[BSS16]

Nikhil Bansal, Aravind Srinivasan, and Ola Svensson.
Lift-and-round to improve weighted completion time on unrelated machines.
In Proceedings of
the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC
2016, Cambridge, MA, USA, June 18-21, 2016, pages 156–167, 2016.
URL:
http://arxiv.org/abs/1511.07826, doi:10.1145/2897518.2897572.

[Chu99]

F. A. Chudak. A min-sum 3/2-approximation algorithm for scheduling unrelated parallel
machines. Journal of Scheduling, 2(2):73–77, 1999.

[GLLK79] Ronald L Graham, Eugene L Lawler, Jan Karel Lenstra, and AHG Rinnooy Kan.
Optimization and approximation in deterministic sequencing and scheduling: a survey.
Annals of discrete mathematics, 5:287–326, 1979.
[GLS93]

Martin Grötschel, Lászlo Lovász, and Alexander Schrijver. Geometric Algorithms and
Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer,
1993.

[Hor73]

W.A. Horn. Minimizing average flow time with parallel machines. Oper. Res., 21:846–
847, 1973.

[HSW01]

Han Hoogeveen, Petra Schuurman, and Gerhard J. Woeginger. Non-approximability
results for scheduling problems with minsum criteria. INFORMS Journal on Computing, 13(2):157–168, 2001. URL: http://dx.doi.org/10.1287/ijoc.13.2.157.10520,
doi:10.1287/ijoc.13.2.157.10520.

[KK86]

Tsuyoshi Kawaguchi and Seiki Kyan. Worst case bound of an LRF schedule for the
mean weighted flow-time problem. SIAM J. Comput., 15(4):1119–1129, 1986. URL:
http://dx.doi.org/10.1137/0215081, doi:10.1137/0215081.

[KMPS09] V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. A unified approach to scheduling on unrelated parallel machines. J. ACM,
56(5):28:1–28:31, 2009.
[Sku01]

Martin Skutella.
Convex quadratic and semidefinite programming
relaxations in scheduling.
J. ACM, 48(2):206–242,
2001.
URL:
http://doi.acm.org/10.1145/375827.375840, doi:10.1145/375827.375840.

[Smi56]

Wayne
E.
Smith.
Various
optimizers
for
single-stage
production.
Naval Research Logistics Quarterly, 3(1-2):59–66, 1956.
URL:
http://dx.doi.org/10.1002/nav.3800030106, doi:10.1002/nav.3800030106.

[SS99]

Jay Sethuraman and Mark S. Squillante. Optimal scheduling of multiclass parallel
machines. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete
Algorithms, 17-19 January 1999, Baltimore, Maryland., pages 963–964, 1999. URL:
http://dl.acm.org/citation.cfm?id=314500.314948.

[SS02]

Andreas S Schulz and Martin Skutella. Scheduling unrelated machines by randomized
rounding. SIAM Journal on Discrete Mathematics, 15(4):450–469, 2002.
21

[ST93]

David B. Shmoys and Éva Tardos.
An approximation algorithm for the
generalized assignment problem.
Math. Program., 62:461–474, 1993.
URL:
http://dx.doi.org/10.1007/BF01585178, doi:10.1007/BF01585178.

[SW99a]

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

[SW99b]

Martin Skutella and Gerhard J. Woeginger. A PTAS for minimizing the weighted sum
of job completion times on parallel machines. In Symposium on Theory of Computing,
STOC, pages 400–407, 1999.

[SW13]

Maxim Sviridenko and Andreas Wiese.
Approximating the ConfigurationLP for minimizing weighted sum of completion times on unrelated machines.
In Integer Programming and Combinatorial Optimization - 16th International
Conference, IPCO 2013, Valparaı́so, Chile, March 18-20, 2013. Proceedings,
pages 387–398, 2013. URL: http://dx.doi.org/10.1007/978-3-642-36694-9_33,
doi:10.1007/978-3-642-36694-9_33.

22

