# Approximating Unrelated Machine Weighted Completion Time Using Iterative
Rounding and Computer Assisted Proofs

Shi Li111The work was supported by State Key Laboratory for Novel Software
Technology, and New Cornerstone Science Laboratory.
Department of Computer Science and Technology
Nanjing University
Nanjing, Jiangsu, China

###### Abstract

We revisit the unrelated machine scheduling problem with the weighted
completion time objective. It is known that independent rounding achieves a
1.5 approximation for the problem, and many prior algorithms improve upon this
ratio by leveraging strong negative correlation schemes. On each machine $i$,
these schemes introduce strong negative correlation between events that some
pairs of jobs are assigned to $i$, while maintaining non-positive correlation
for all pairs.

Our algorithm deviates from this methodology by relaxing the pairwise non-
positive correlation requirement. On each machine $i$, we identify many groups
of jobs. For a job $j$ and a group $B$ not containing $j$, we only enforce
non-positive correlation between $j$ and the group as a whole, allowing $j$ to
be positively-correlated with individual jobs in $B$. This relaxation suffices
to maintain the 1.5-approximation, while enabling us to obtain a much stronger
negative correlation within groups using an iterative rounding procedure: at
most one job from each group is scheduled on $i$.

We prove that the algorithm achieves a $(1.36+\epsilon)$-approximation,
improving upon the previous best approximation ratio of $1.4$ due to Harris.
While the improvement may not be substantial, the significance of our
contribution lies in the relaxed non-positive correlation condition and the
iterative rounding framework. Due to the simplicity of our algorithm, we are
able to derive a closed form for the weighted completion time our algorithm
achieves with a clean analysis. Unfortunately, we could not provide a good
analytical analysis for the quantity; instead, we rely on a computer assisted
proof. Nevertheless, the checking algorithm for the analysis is easy to
implement, essentially involving evaluation of maximum values of single-
variable quadratic functions over given intervals. Therefore, unlike previous
results which use intricate analysis to optimize the final approximation
ratio, we delegate this task to computer programs.

##  1 Introduction

The unrelated machine weighted completion time problem is a classic problem in
scheduling theory. We are given a set $J$ of $n$ jobs and a set $M$ of $m$
machines. Each job $j\in J$ has a weight $w_{j}\in{\mathbb{R}}_{>0}$, and
there is a $p_{ij}\in{\mathbb{R}}_{>0}\cup\\{\infty\\}$ for every $i\in M$ and
$j\in J$, indicating the processing time needed to process $j$ on machine $i$;
sometimes $p_{ij}$ is also called the size of $j$ on $i$. The goal of the
problem is to schedule the $n$ jobs $J$ on the $m$ machines $M$, so as to
minimize the total weighted completion time over all jobs. It is well-known
that once we have an assignment $\phi:J\to M$ of jobs to machines, it is
optimum to schedule the jobs $j\in\phi^{-1}(i)$ on each $i\in M$ in descending
order of $\frac{w_{j}}{p_{ij}}$, i.e., Smith ratios. Therefore, it suffices to
use the function $\phi:J\to M$ to denote a solution, and its weighted
completion time is

$\displaystyle\sum_{i\in
M}\Big{(}\sum_{j\in\sigma^{-1}(i)}p_{ij}w_{j}+\sum_{\\{j,j^{\prime}\\}\subseteq\sigma^{-1}(i):j\neq
j^{\prime}}\min\\{p_{ij}w_{j^{\prime}},p_{ij^{\prime}}w_{j}\\}\Big{)}.$

The problem was proved to be strongly NP-hard and APX-hard [10], and several
mathematical programming based algorithms gave a $1.5$-approximation ratio for
the problem [18, 21, 20]. The algorithms use the following independent
rounding framework: solve a linear/convex/semi-definite program to obtain a
fractional assignment $(x_{ij})_{i\in M,j\in J}$ of jobs to machines, and then
randomly and independently assign each job $j$ to a machine $i$, with
probabilities $x_{ij}$. A simple example shows that independent rounding can
only lead to a 1.5-approximation, even if the fractional assignment is in the
convex hull of integral assignments. It was a longstanding open problem to
break the approximation factor of 1.5 [5, 18, 15, 23, 19].

In a breakthrough result, Bansal et al. [2] solved the open problem by giving
a $(1.5-10^{-7})$-approximation for the problem using their novel strong
negative correlation rounding scheme. They solve a SDP relaxation for the
problem to obtain the fractional assignment $(x_{ij})_{i\in M,j\in J}$. If two
jobs $j$ and $j^{\prime}$ are assigned to the same machine $i$, then one will
delay the other; this happens with probability $x_{ij}x_{ij^{\prime}}$ in the
independent rounding algorithm. To improve the approximation ratio of $1.5$,
they define some groups of jobs for each machine $i$. For two distinct jobs
$j$ and $j^{\prime}$, they guarantee the probability that $j$ and $j^{\prime}$
are both assigned to $i$ is at most $x_{ij}x_{ij^{\prime}}$, and at most
$(1-\xi)x_{ij}x_{ij^{\prime}}$ for some absolute constant $\xi>0$, if $j$ and
$j^{\prime}$ are in a same group. In other words, they introduced strong
negative correlation between pairs within the same group while maintaining
non-positive correlation between all pairs.

Since the seminal work of Bansal et al. [2], there has been a series of
efforts aimed at improving the approximation ratio using strong negative
correlation schemes. Li [17] combined the scheme of Bansal et al. with a time-
indexed LP relaxation, to give an improved the approximation ratio to
$1.5-1/6000$. Subsequently, Im and Shadloo [13] developed a scheme inspired by
the work of Feige and Vondrak [7], further improving the approximation ratio
to $1.488$. More recently, Im and Li [12] introduced a strong negative
correlation scheme by borrowing ideas from the online correlated selection
technique for online edge-weighted bipartite matching [6], and further
improved the ratio to $1.45$. Both of the results use the time-indexed LP
relaxation. The current state-of-the-art result is a 1.4-approximation
algorithm given by Harris [9], based on the SDP relaxation and a novel
dependent rounding scheme developed by the author.

#### Our Results

While prior better-than-1.5 approximation algorithms leveraged various strong
negative correlation schemes, they all share the common principle we
highlighted: introducing strong negative correlation between intra-group pairs
of jobs, while maintaining non-positive correlation between all pairs. Our
algorithm deviates from this approach by introducing a more relaxed version of
the non-positive correlation requirement. Specifically, in some cases, we only
require non-positive correlation to hold between a job $j$ and a group as a
whole entity, instead of individual jobs in the group: for a machine $i$,
conditioned on $j$ being assigned to $i$, the expected total size of jobs in
the group assigned to $i$ is at most the unconditional counterpart. With this
relaxed notion of non-positive correlation, we can design a novel and simple
iterative rounding procedure, that ensures at most one job from each group is
assigned to $i$. This gives the strongest possible negative correlation within
each group, leading to our improved approximation algorithm:

######  Theorem 1.1.

There is a polynomial time randomized $(1.36+\epsilon)$-approximation
algorithm for the unrelated machine weighted completion time scheduling
problem for any constant $\epsilon>0$.

While our improvement over the prior best ratio of $1.4$ may not be
substantial, we believe the significance of our contribution lies in the
relaxed non-positive correlation condition and the iterative rounding
framework. The algorithm performs one of two operations in each iteration, and
terminates with an integral solution when no operations can be performed. In
contrast, previous algorithms need to design various strong negative
correlation schemes, often involving some complex procedures. In these
schemes, the parameter $\xi$ in the probability $(1-\xi)x_{ij}x_{ij^{\prime}}$
that two jobs in a same group tends to be small, while our procedure
guarantees $\xi=1$.

Due to the simplicity of our algorithm, we are able to derive a closed form
for the weighted completion time the algorithm provides with a clean analysis.
Unfortunately, we could not provide a good analytical analysis for the ratio
between the derived quantity and the LP cost; instead, we rely on a computer
assisted proof. Nonetheless, the checking algorithm for the analysis is easy
to implement, essentially involving the evaluation of maximum values of
single-variable quadratic functions over given intervals. This leads to
another advantage of our result: while previous results use involved analysis
to optimize the approximation ratio, we delegate the tasks of optimizing the
verifying the ratio to computer programs.

Finally, it is worth noting two features of our algorithm. Firstly, it is the
first algorithm to leverage the condition that the weights $w_{j}$’s are
independent of machines. Prior algorithms do not use this condition and thus
they are capable of solving the more general scheduling problem where we also
have machine-dependent weights $w_{ij}$. Secondly, our algorithm is based on
the configuration LP relaxation for the problem, marking the first use of this
relaxation in designing improved approximation algorithms for the scheduling
problem.

#### Overview of Our Algorithm and Analysis

For the sake of convenience, we swap job sizes and weights to obtain a
scheduling instance with machine-independent job sizes $p_{j}$, but machine
dependent weights $w_{ij}$. It is a simple observation that the swapping does
not change the instance. We solve the configuration LP to obtain a fractional
assignment $(z_{ij})_{i\in M,j\in J}$.

With the relaxed non-positive correlation condition, we design our iterative
rounding algorithm as follows. Let $G=(M,J,E)$ be the support bipartite graph
of $z$. The volume of an edge $ij$ is defined as $p_{j}z_{ij}$, and we use
$\mathrm{vol}(E^{\prime})$ to denote the total volume edges in $E^{\prime}$
for every $E^{\prime}\subseteq E$. We partition jobs into classes based on
their sizes geometrically, with a random shift: a job $j$ is in
$J_{k},k\in{\mathbb{Z}}$, if we have
$p_{j}\in[\beta\rho^{k},\beta\rho^{k+1})$, for some $\rho>1$ and a randomly
chosen $\beta\in[1,\rho)$.

Our iterative rounding algorithm handles each job class $J_{k}$ separately and
independently; henceforth we fix $k$. For every machine $i$, let
$\delta^{k}_{i}$ be the set of edges between $i$ and $J_{k}$. We sort the
edges $ij\in\delta^{k}_{i}$ in descending order of their
$\frac{w_{ij}}{p_{j}}$ values, i.e., Smith ratios. We _mark_ the first
$\rho\beta^{k}$ volume the edges in this order, or all edges in
$\delta^{k}_{i}$ if $\mathrm{vol}(\delta^{k}_{i})\leq\beta\rho^{k}$; the other
edges in $\delta^{k}_{i}$ are _unmarked_. Let $\delta^{k,\mathrm{mk}}_{i}$ be
the set of marked edges in $\delta^{k}_{i}$. In the actual algorithm, we may
need to break some edge into two parallel edges, one marked and other
unmarked. For simplicity, we assume this does not happen in the overview.

We maintain a $\bar{x}_{ij}$ value for every $ij\in E$ between $M$ and
$J_{k}$, initially set to $z_{ij}$. Let $\bar{G}=(M,J_{k},\bar{E})$ be the
support of $\bar{x}$. A crucial property we maintain is that
$\sum_{e\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}_{e}p_{e}$ does not change (we
define $p_{e}=p_{j}$ if $e=ij$), until when
$|\delta^{k,\mathrm{mk}}_{i}\cap\bar{E}|=1$ happens. Two operations respecting
the property can be defined: a rotation operation over a cycle of marked edges
in $\bar{E}$, and a shifting operation along a “pseudo-marked-path” in
$\bar{E}$. Both operations are random and respect the marginal probabilities,
and the condition that the every job is assigned to an extent of 1. As the
former operation is standard, we only describe the latter. A pseudo-marked-
path consists of a simple path $(j_{1},i_{1},j_{2},i_{2}\cdots,i_{t-1},j_{t})$
of edges in $\bar{E}$ between two machines $j_{1}$ and $j_{t}$, with one edge
$i_{0}j_{1}$ at the beginning and one edge $j_{t}i_{t}$ in the end. The edge
$i_{0}j_{1}$ may be unmarked, in which case we allow
$i_{0}\in\\{i_{1},i_{2},\cdots,i_{t-1}\\}$, or the unique edge in
$\delta^{k,\mathrm{mk}}_{i_{0}}\cap\bar{E}$. The same requirement is imposed
on $j_{t}i_{t}$. Naturally, we shift $\bar{x}$-values on the path in one of
the two directions randomly. Each operation will remove at least 1 edge from
$\bar{G}$, and the procedure terminates when we have no cycles of marked edges
or pseudo-marked-paths in $\bar{E}$. We prove that when this happens, the
$\bar{x}$-vector is integral, which gives the assignment of $J_{k}$ to $M$.

Now we focus on the correlation between two edges in $\delta^{k}_{i}$. Two
unmarked edges have a non-positive correlation. Positive correlations may be
introduced between an unmarked edge and a marked one by the shifting operation
along a pseudo-marked path. It may happen that $i_{1}j_{1}$ is unmarked and
$i_{1}$ is the same as some $i_{o}$ on the path. Then $i_{1}j_{1}$ and
$i_{o}j_{o}$ will be positively related. However, the quantity
$\sum_{e\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}_{e}p_{e}$ does not change; that
is, $j$ is non-positively correlated with $\delta^{k,\mathrm{mk}}_{i}$ as a
whole. This is where the relaxed non-positive correlation condition comes into
play. As all the marked edges precede unmarked ones in the final schedule,
this suffices to preserve the $1.5$-approximation ratio. The improvement over
1.5 arises from the strong negative correlation among marked edges. We
maintain
$\sum_{e\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}_{e}p_{e}\leq\beta\rho^{k}$ until
$\delta^{k,\mathrm{mk}}_{i}\cap\bar{E}$ becomes a singleton. As every
class-$k$ job has size at least $\beta\rho^{k}$, at most one edge in
$\delta^{k,\mathrm{mk}}_{i}$ will be chosen in our final schedule, resulting
in the strongest possible negative correlation within
$\delta^{k,\mathrm{mk}}_{i}$.

For the analysis, we derive a relatively simple closed form for the expected
total weighted completion time. We can separately focus on each machine $i$, a
threshold $\sigma$ on the Smith ratio, and all the jobs $j$ with
$\frac{w_{ij}}{p_{i}}\geq\sigma$, denoting them as $J^{\prime}$. The term
leading to the improvement over $1.5$ is precisely expressed as
$\frac{1}{2}\sum_{k}\big{(}\mathrm{vol}(\delta^{k,\mathrm{mk}}_{i}\cap
J^{\prime})\big{)}^{2}=\frac{1}{2}\sum_{k}\big{(}\min\big{\\{}\mathrm{vol}\big{(}\delta^{k}_{i}\cap
J^{\prime}),\beta\rho^{k}\big{\\}}\big{)}^{2}$. While this term is simple, we
still encounter difficulties in providing a good analytical analysis of our
ratio.

Instead, we provide a computer assisted proof with $\rho=2$. We only focus on
three most important job classes $k$, disregarding the savings from others.
The ratio is captured by some mathematical program with a maximization
objective. Depending on whether
$\mathrm{vol}(\delta^{k,\mathrm{mk}}_{i})=\mathrm{vol}(\delta^{k}_{i})$ or
$\mathrm{vol}(\delta^{k,\mathrm{mk}}_{i})=\beta\rho^{k}_{i}$ for each of the
three classes $k$, we further partition the program into three sub-programs.
By specifying some Lagrangian multipliers for the sub-programs, we establish
upper bounds on the sub-programs, and thus the original program. This results
in our $(1.36+\epsilon)$-approximation ratio. A computer program verifies the
validity of all the multipliers and upper bounds. The checker algorithm is
easy to implement; essentially, it involves checking hundreds of quadratic
function problems, each asking for the maximum value of a single-variable
quadratic function over an interval.

#### Other Related Work

The unrelated machine weighted completion time problem can be solved in
polynomial time if jobs have the same weights or if $p_{ij}\in\\{1,\infty\\}$
for every $ij$ pair [11, 3]. When $m=1$, the Smith rule gives the optimum
schedule. Additionally, when $m=O(1)$ there exists a polynomial-time
approximation scheme (PTAS) [16]. For the problem where weights also depend on
the machines and $w_{ij}=p_{ij}$ for every $i\in M,j\in J$, Kalaitzis et al.
developed a 1.21-approximation algorithm [14]; in this case, all jobs have the
same Smith ratios on all machines. For the cases where the machines are
identical, or uniformly related, the problem remains NP-hard [8] but admit
PTASes [1, 22, 4].

#### Organization

The rest of the paper is organized as follows. In Section 2, we describe our
iterative rounding algorithm for the scheduling problem, and show that it
terminates with an integral assignment. In Section 3, we establish an upper
bound on the weighted completion time given by our algorithm. In Section 4, we
compare the upper bound and the LP cost to obtain our approximation ratio. It
suffices to focus on a fixed machine $i$, and the set of jobs whose Smith
ratios are above some threshold on $i$. We conclude with some open problems in
Section 5.

##  2 Iterative Rounding for Unrelated Machine Weighted Completion Time
Scheduling

We describe our iterative rounding algorithm for the unrelated machine
weighted time scheduling problem.

###  2.1 Swapping Job Sizes and Weights

At the very beginning of our algorithm, we swap job sizes and weights so that
in the new instance, a job $j$ has a fixed size $p_{j}$, but machine-dependent
weights $w_{ij}$’s. To achieve this goal, we consider the general problem
where both sizes and weights depend on the machines: We are given a weight
$w_{ij}>0$ and a processing time $p_{ij}>0$ for every $i\in M$ and $j\in C$.
We need to find an assignment $\phi:J\to M$ of jobs to machines. On every
machine $i$, we consider the schedule of jobs $\phi^{-1}(i)$ using the Smith
rule, with job processing times $(p_{ij})_{j\in\phi^{-1}(i)}$ and weights
$(w_{ij})_{j\in\phi^{-1}(i)}$. This gives us a weighted completion time for
machine $i$; the objective we try to minimize is the sum of this quantity over
all machines $i$.

A simple but useful observation we use is the following:

######  Lemma 2.1.

Consider two instances $\mathcal{I}$ and $\mathcal{I}^{\prime}$ of the general
weighted completion time problem on the same set $M$ of machines and the same
set $J$ of jobs. $\mathcal{I}$ has processing times $p_{ij}$ and weights
$w_{ij}$, and $\mathcal{I}^{\prime}$ has processing times $p^{\prime}_{ij}$
and weights $w^{\prime}_{ij}$. For every $i\in M,j\in J$, we have
$p_{ij}=w^{\prime}_{ij}$ and $w_{ij}=p^{\prime}_{ij}$. Then for every
$\phi:J\to M$ , the cost of $\phi$ for $\mathcal{I}$ is the same as that for
$\mathcal{I}^{\prime}$.

###### Proof.

For every machine $i$, define $\prec_{i}$ to be the total order over $J$ w.r.t
the Smith ratios on machine $i$ in instance $\mathcal{I}$. That is, for every
$j,j^{\prime}\in J,j\neq j^{\prime}$, $j\prec_{i}j^{\prime}$ holds if and only
if $j$ should be processed before $j^{\prime}$ if they are both assigned to
$i$ in the instance $\mathcal{I}$. This implies
$\frac{w_{ij}}{p_{ij}}\geq\frac{w_{ij^{\prime}}}{p_{ij^{\prime}}}$; for two
jobs with the same Smith ratio, we break the tie arbitrarily. Define
$\prec^{\prime}_{i}$ in the same way but for the instance
$\mathcal{I}^{\prime}$. Then, we can guarantee $j\prec_{i}j^{\prime}$ if and
only if $j^{\prime}\prec^{\prime}_{i}j$ for every $i\in M,j,j^{\prime}\in
J,j\neq j^{\prime}$.

The cost of any $\phi:J\to M$ w.r.t $\mathcal{I}$ is

$\displaystyle\sum_{i\in M,j,j^{\prime}\in\phi^{-1}(i):j=j^{\prime}\text{ or
}j\prec_{i}j^{\prime}}p_{ij}w_{ij^{\prime}}\quad$
$\displaystyle=\quad\sum_{i\in
M,j,j^{\prime}\in\phi^{-1}(i):j=j^{\prime}\text{ or
}j^{\prime}\prec^{\prime}_{i}j}w^{\prime}_{ij}p^{\prime}_{ij^{\prime}}$
$\displaystyle=\sum_{i\in M,j,j^{\prime}\in\phi^{-1}(i):j=j^{\prime}\text{ or
}j\prec^{\prime}_{i}{j^{\prime}}}p^{\prime}_{ij}w^{\prime}_{ij^{\prime}}\ .$

which is precisely the cost of $\phi$ w.r.t $\mathcal{I}^{\prime}$. ∎

Therefore, swapping the job sizes and weights does not change the instance. In
the standard unrelated machine weighted completion time problem, the weights
are machine-indepdent. By the lemma, it is equivalent to the problem where
weights may depend on machines but job sizes are machine-independent.

From now on, we focus on such an instance. Every job $j$ has a fixed size
$p_{j}>0$, but machine-dependent weights $(w_{ij})_{i\in M}$. We remark that
the swapping is only for the sake of convenience, as one could obtain an
equivalent algorithm without swapping them. As in [2] and [9], we shall
partition jobs into classes according to their sizes, and machine-independent
sizes will ensure a global partition. Without the swapping, we have to
partition the jobs according to their weights, which is incompatible with
prior algorithms. Also, our algorithm crucially depends on that sizes are
machine-independent after swapping. So, unlike prior algorithms, ours does not
work for the general scheduling problem.

We shall use $p(J^{\prime}):=\sum_{j\in J^{\prime}}p_{j}$ for every
$J^{\prime}\subseteq J$ to denote the total size of jobs in $J^{\prime}$.

###  2.2 Configuration LP

We describe the configuration LP for the problem. As usual, a configuration
$f$ is a subset of $J$. For every $i\in M,f\subseteq J$, we define
$\mathrm{cost}_{i}(f)$ to be the total weighted completion time of scheduling
jobs $f$ on machine $i$ optimally, i.e., using the Smith rule. Then in the
configuration LP, we have a variable $y_{if}$ for every machine $i\in M$ and
configuration $f\subseteq J$, indicating if the set of jobs assigned to $i$ is
precisely $f$. The LP is as follows:

$\min\quad\sum_{i\in M}\sum_{f}y_{if}\cdot\mathrm{cost}_{i}(f)$ (1)

$\displaystyle\sum_{f}y_{if}$ $\displaystyle=1$ $\displaystyle\forall i\in M$
(2) $\displaystyle\sum_{i\in M}\sum_{f\ni j}y_{if}$ $\displaystyle=1$
$\displaystyle\forall j\in J$ (3)

$\displaystyle y_{if}$ $\displaystyle\geq 0$ $\displaystyle\forall i\in M,j\in
J$ (4)

(2) requires that for every machine $i\in M$, we choose exactly one
configuration $f$. (3) requires that every job is covered by exactly one
configuration across all machines. (4) is the non-negativity constraint. We
pay a cost of $\mathrm{cost}_{i}(f)$ on $i$ if the set of jobs assigned to $i$
is $f$, thus we have the objective (1).

Though this LP has exponential number of variables, Sviridenko and Wiese [23]
showed that it can be solved approximately within a factor of $1+\epsilon$,
for any constant $\epsilon>0$. So, we assume we are given a
$(1+\epsilon)$-approximate solution $y$ to the LP; in particular, the result
of [23] suggests that the number of non-zeros in $y$ is small.

For every $i\in M$ and $j\in J$, we let $z_{ij}:=\sum_{f\ni j}y_{if}$ denote
the fraction of job $j$ assigned to machine $i$. We only use $z$ variables in
the rounding algorithm, while reserving the $y_{if}$ variables for the
analysis.

###  2.3 Partition of Jobs into Classes and Construction of Bipartite Graph
$G$ with Marked and Unmarked Edges

Let $\rho$ be a constant which will be set to $2$ later; for future reference
we present the algorithm and a part of the analysis for a general $\rho>1$. We
randomly choose a $\beta\in[1,\rho)$ such that $\ln\beta$ is uniformly
distributed in $[0,\ln\rho)$. For an integer $k$, we say a job $j$ is in class
$k$ if $p_{j}\in[\beta\rho^{k},\beta\rho^{k+1})$. Let $J_{k}$ be the set of
jobs in class $k$; notice that it depends on the randomly chosen $\beta$. Once
$\beta$ is chosen, we have a global partition $(J_{k})_{k}$ of jobs,
independent of the machines.

We construct a bipartite multi-graph $G=(M,J,E)$ between $M$ and $J$, along
with a vector $x\in(0,1]^{E}$. Each edge in $E$ is either _marked_ or
_unmarked_. The procedure is formally described in Algorithm 1.

Algorithm 1 Construction of $G$, and vector $x\in(0,1]^{E}$

1:let $E\leftarrow\emptyset$

2:for every $k$ with $J_{k}\neq\emptyset$ and every $i\in M$ do

3: $v\leftarrow 0$

4: sort jobs in $J_{k}$ in descending order of the Smith ratios on machine $i$
(i.e., values of $\frac{w_{ij}}{p_{j}}$)

5: for every job $j\in J_{k}$ in the order, if $z_{ij}>0$ then do

6: if $v+p_{j}z_{ij}\leq\beta\rho^{k}$ then

7: add to $E$ a _marked edge_ $e$ between $i$ and $j$ with $x_{e}=z_{ij}$

8: else if $v\geq\beta\rho^{k}$ then

9: add to $E$ an _unmarked edge_ $e$ between $i$ and $j$ with $x_{e}=z_{ij}$

10: else$\triangleright$ We have $v<\beta\rho^{k}<v+p_{j}z_{ij}$

11: add to $E$ a _marked edge_ $e$ between $i$ and $j$ with
$x_{e}=\frac{\beta\rho^{k}-v}{p_{j}}$

12: add to $E$ an _unmarked edge_ $e^{\prime}$ between $i$ and $j$ with
$x_{e^{\prime}}=z_{ij}-x_{e}=\frac{v+p_{j}z_{ij}-\beta\rho^{k}}{p_{j}}$

13: $v\leftarrow v+p_{j}z_{ij}$

14:return $G:=(M,J,E)$ and $x\in(0,1]^{E}$

#### Notations

With $G=(M,J,E)$ and $x\in(0,1]^{E}$ constructed, we define the following
notations. For every $e=ij\in E$, we define $p_{e}=p_{j}$ to be the size of
its incident job, and $\sigma_{e}=\frac{w_{ij}}{p_{j}}$ be the Smith ratio.
For every $i\in M$ (resp., $j\in J$), let $\delta_{i}$ (resp., $\delta_{j}$)
be the set of edges in $E$ incident to $i$ (resp., $j$). For every job class
$k$, let $E_{k}$ be the set of edges in $E$ between $M$ and $J_{k}$,
$G_{k}=(M,J_{k},E_{k})$ and $x^{(k)}\in(0,1]^{E_{k}}$ be the $x$ vector
restricted to $E_{k}$. For every $k$ and $i\in M$, let
$\delta^{k}_{i}=\delta_{i}\cap E_{k}$ be incident edges of $i$ in $E_{k}$. We
use superscripts “$\mathrm{mk}$” and “$\mathrm{umk}$” to denote the
restrictions to marked and unmarked edges respectively: $E^{\mathrm{mk}}$ and
$E^{\mathrm{umk}}$ are the sets of marked and unmarked edges in $E$
respectively.
$\delta^{\mathrm{mk}}_{i}:=E^{\mathrm{mk}}\cap\delta_{i},\delta^{k,\mathrm{mk}}_{i}:=E^{\mathrm{mk}}\cap\delta^{k}_{i}$
and $\delta^{\mathrm{mk}}_{j}=E^{\mathrm{mk}}\cap\delta_{j}$; the same rule
applies to unmarked edges as well.

######  Definition 2.2.

For every $e\in E$, the _volume_ of $e$ is defined as
$\mathrm{vol}(e):=x_{e}p_{e}$. For a subset $E^{\prime}\subseteq E$ of edges,
we define $\mathrm{vol}(E^{\prime})=\sum_{e\in E^{\prime}}\mathrm{vol}(e)$.

We elaborate on Algorithm 1 by describing it using an alternative way. For
every $i\in M,j\in J$ with $z_{ij}>0$, we create an edge $ij$ with
$x_{ij}=z_{ij}$. For every job class $k$, and on every machine $i$, we sort
the edges $e\in\delta^{k}_{i}$ according to $\sigma_{e}$ in descending order.
We find an integer $t$ such that the total volume of the first $t$ edges in
this order is exactly $\beta\rho^{k}$; assume for now $t$ exists. We mark the
$t$ edges; the other edges in $\delta^{k}_{i}$ are unmarked. If the integer
$t$ does not exist, we only mark a portion of some edge $e$ in the order. So,
in this case, we break $e$ into two parallel edges, one marked and the other
unmarked, and split the $x$-value (Steps 11 and 12), so that the volume of
marked edges is exactly $\beta\rho^{k}$. In case
$\mathrm{vol}(\delta^{k}_{i})\leq\beta\rho^{k}$, all edges in $\delta^{k}_{i}$
are marked. See Figure 1 for an illustration of the construction of $G$.

Figure 1: The edges in $G$ between $i$ and $J_{k}$ for the case
$\mathrm{vol}(\delta^{k}_{i})\geq\beta\rho^{k}$, where we have
$\mathrm{vol}(\delta^{k,\mathrm{mk}}_{i})=\beta\rho^{k}$.

So, the total $x$-value of edges between any $j\in J$ and $i\in M$ is
precisely $z_{ij}$. This implies $\sum_{e\in\delta_{j}}x_{e}=1$ for every
$j\in J$. As we are dealing with multi-graphs, when we use $ij$ to denote an
edge, we assume we know its identity. The following claim is straightforward:

######  Claim 2.3.

For every job class $k$ and machine $i\in M$, we have
$\mathrm{vol}(\delta^{k,\mathrm{mk}}_{i})=\min\big{\\{}\mathrm{vol}(\delta^{k}_{i}),\beta\rho^{k}\big{\\}}$.

The threshold $\beta\rho^{k}$ for $\mathrm{vol}(\delta^{k,\mathrm{mk}}_{i})$
was carefully chosen as the lower bound for the size of a class-$k$ job.

###  2.4 Iterative Rounding

We describe our randomized iterative rounding procedure to assign jobs to
machines. It handles jobs in different classes separately and independently.
So, throughout this section, we fix a job class $k$, and show how to assign
jobs $J_{k}$.

######  Definition 2.4.

Let $\bar{G}=(M,J_{k},\bar{E}\subseteq E_{k})$ be a spanning subgraph of
$G_{k}$. A pseudo-marked-path in $\bar{G}$ is a (not-necessarily-simple) path
$(i_{0},j_{1},i_{1},\cdots,j_{t},i_{t})$ of distinct edges in $\bar{G}$, where
$i_{0},i_{1},\cdots,i_{t}\in M$ and $j_{1},j_{2},\cdots,j_{t}\in J_{k}$,
satisfying the following properties.

  * •

The sub-path $(j_{1},i_{1},…,i_{t-1},j_{t})$ is simple, and all the edges on
it are marked. (It is possible that $t=1$, in which case the sub-path consists
of a single job.)

  * •

The edge $i_{0}j_{1}$ on the path is either unmarked, or the only edge in
$\delta^{k,\mathrm{mk}}_{i_{0}}\cap\bar{E}$.

  * •

The edge $j_{t}i_{t}$ on the path is either unmarked, or the only edge in
$\delta^{k,\mathrm{mk}}_{i_{t}}\cap\bar{E}$.

We remark that in the case where $i_{0}j_{1}$ is unmarked, it is possible that
$i_{0}\in\\{i_{1},i_{2},\cdots,i_{t-1}\\}$. So, the path may not be simple.
However, in the other case where $i_{0}j_{1}$ is the only edge in
$\delta^{\mathrm{mk}}_{i_{0}}\cap\bar{E}$, we have
$i_{0}\notin\\{i_{1},i_{2},\cdots,i_{t-1}\\}$, as every machine in the set has
at least 2 incident marked edges in $\bar{E}$. The same argument can be made
to the last edge $j_{t}i_{t}$. See Figure 2 for an illustration of a pseudo-
marked path.

Figure 2: The three cases for the machine $i_{0}$ on a pseudo-marked path in
$\bar{G}=(M,J^{k},\bar{E})$. They also apply to the machine $i_{t}$.
Algorithm 2 Iterative Rounding Procedure for Job Class $k$

1:$\bar{x}\leftarrow x^{(k)},\bar{E}\leftarrow E_{k},\bar{G}\leftarrow G_{k}$
$\triangleright$ We maintain that $\bar{G}=(M,J_{k},\bar{E})$ and $\bar{E}$ is
the support of $\bar{x}\in[0,1]^{E_{k}}$

2:while true do

3: if we can find a simple cycle
$(i_{0},j_{1},i_{1},j_{2},i_{2},\cdots,j_{t},i_{t}=i_{0})$ of marked edges in
$\bar{G}$, or a semi-marked path $(i_{0},j_{1},i_{1},\cdots,j_{t},i_{t})$ in
$\bar{G}$ then

4: define a non-zero vector $a\in{\mathbb{R}}^{E_{k}}$ as in the text

5: choose the largest $\theta>0$ such that $\bar{x}+\theta a$ is non-negative

6: choose the largest $\theta^{\prime}>0$ such that $\bar{x}-\theta^{\prime}a$
is non-negative

7: with probability $\frac{\theta^{\prime}}{\theta+\theta^{\prime}}$, let
$\bar{x}\leftarrow\bar{x}+\theta a$; with the remaining probability
$\frac{\theta}{\theta+\theta^{\prime}}$, let
$\bar{x}\leftarrow\bar{x}-\theta^{\prime}a$

8: for every $e\in\bar{E}$ with $\bar{x}_{e}=0$ do: remove $e$ from $\bar{E}$
and $\bar{G}$

9: else break

With the definition, we can describe the iterative rounding procedure for
$J_{k}$. The pseudo-code is given in Algorithm 2. We need to describe how to
define the non-zero vector $a\in{\mathbb{R}}^{E_{k}}$ in Step 4. Suppose the
structure (cycle or pseudo-marked-path) we found in $\bar{G}$ is
$(i_{0},j_{1},i_{1},j_{2},i_{2},\cdots,j_{t},i_{t}=i_{0})$ in $\bar{G}$. We
define a non-zero vector $a\in{\mathbb{R}}^{E_{k}}$ so that the following
conditions hold.

  * •

Every edge $e\in\bar{E}$ not on the structure has $z_{e}=0$.

  * •

For every $o\in[t]$, we have $a_{i_{o-1}j_{o}}+a_{j_{o}i_{o}}=0$.

  * •

If the structure is a cycle, then for every $o\in[t]$, we have
$a_{j_{o}i_{o}}p_{j_{o}}+a_{i_{o}j_{o+1}}p_{j_{o+1}}=0$, where for convenience
we assume $j_{t+1}=j_{1}$.

  * •

If the structure is a pseudo-marked-path, then for every $o\in[t-1]$, we have
$a_{j_{o}i_{o}}p_{j_{o}}+a_{i_{o}j_{o+1}}p_{j_{o+1}}=0$.

In words, the support of $a$ is structure. For a job $j$ on the structure, the
sum of $a$-values of its two incident edges on the cycle is $0$. If the
structure is a cycle, then for any machine $i$ on the cycle, the sum of
$a_{ij}p_{j}$ over its two incident edges $ij$ on the cycle is $0$. If the
structure is a pseudo-marked-path, we require the equality to hold for
machines in $\\{i_{1},i_{2},\cdots,i_{t-1}\\}$ and its two incident marked
edges on the path. It is easy to see that such $a$ exists and is unique up to
scaling.

The properties for the $a$ vector constructed in either case are summarized in
the following claim.

######  Claim 2.5.

The non-zero $a$-vector constructed in Step 4 of some iteration satisfies the
following properties:

  1. (2.5a)

For every $j\in J_{k}$, we have $\sum_{e\in\delta_{j}}a_{j}=0$.

  2. (2.5b)

For every $i\in M$, if $|\delta^{k,\mathrm{mk}}_{i}\cap\bar{E}|\geq 2$ at the
beginning of the iteration, then
$\sum_{e\in\delta^{k,\mathrm{mk}}_{i}}a_{e}p_{e}=0$.

###### Proof.

The first statement and the second statement for when the structure is a cycle
holds trivially. So, we focus on the second statement when the structure we
found is a pseudo-marked-path $(i_{0},j_{1},i_{1},\cdots,j_{t},i_{t})$. If
$i\in\\{i_{1},i_{2},\cdots,i_{t-1}\\}$, then the equality holds. So assume
$i\notin\\{i_{1},i_{2},\cdots,i_{t-1}\\}$. If $i\notin\\{i_{0},i_{t}\\}$, then
all edges in $\delta^{k,\mathrm{mk}}_{i}$ has $a$ values being $0$. So assume
$i\in\\{i_{0},i_{t}\\}$. Then it must be the case that the edge(s) incident to
$i$ on the pseudo-marked-path are unmarked, since otherwise
$|\delta^{k,\mathrm{mk}}_{i}\cap\bar{E}|=1$ by the definition of a pseudo-
marked-path. This contradicts the premise of the statement. So, in this case
all edges in $\delta^{k,\mathrm{mk}}_{i}$ has $a$ values being $0$. ∎

We observe that the algorithm will terminate in polynomial number of
iterations, as in every iteration of the while loop, we will remove at least
one edge from $\bar{E}$.

###  2.5 Helper Lemmas

Before we conclude that the final $\bar{x}$ given by Algorithm 2 is integral,
we prove some useful lemmas. Some of them will be used in the analysis of the
approximation ratio in Section 3. Till the end of this section, we fix the
random choice $\beta\in[1,\rho)$, which determines $J_{k}$’s, $G$ and $x$. We
use $\widehat{\operatorname*{\mathbb{E}}}[\cdot]$ to denote
$\operatorname*{\mathbb{E}}[\cdot|\beta]$, the expectation condition on a
fixed $\beta$. Then, we fix a job class $k$, and focus on an iteration of the
while loop in Algorithm 2 for this $k$. We assume the if condition holds. Let
$\bar{x}^{{\mathrm{old}}}$ and $\bar{x}^{\mathrm{new}}$ be the $\bar{x}$
values at the beginning and end the iteration respectively. We use
$\operatorname*{\mathbb{E}}^{\prime}[\cdot]$ to denote the expectation over
the randomness in this iteration.

######  Claim 2.6.

For every $e\in E^{k}$, we have
$\operatorname*{\mathbb{E}}^{\prime}[\bar{x}^{\mathrm{new}}_{e}]=\bar{x}^{{\mathrm{old}}}_{e}$.

###### Proof.

This follows from the way we update $\bar{x}$ in the iteration:
$\bar{x}^{\mathrm{new}}_{e}-\bar{x}^{\mathrm{old}}_{e}$ is $\theta a_{e}$ with
probability $\frac{\theta^{\prime}}{\theta+\theta^{\prime}}$, and
$-\theta^{\prime}a_{e}$ with probability
$\frac{\theta}{\theta+\theta^{\prime}}$. So
$\operatorname*{\mathbb{E}}^{\prime}[\bar{x}^{\mathrm{new}}_{e}-\bar{x}^{\mathrm{old}}_{e}]=0$.
∎

######  Claim 2.7.

For every $j\in J_{k}$, we always have
$\sum_{e\in\delta_{j}}\bar{x}^{\mathrm{new}}_{e}=\sum_{e\in\delta_{j}}\bar{x}^{\mathrm{old}}_{e}$.

###### Proof.

This follows from the first statement of Claim 2.5. ∎

######  Claim 2.8.

For a machine $i$, and two distinct edges
$e,e^{\prime}\in\delta^{k,\mathrm{umk}}_{i}$, we have
$\operatorname*{\mathbb{E}}^{\prime}[\bar{x}^{\mathrm{new}}_{e}\bar{x}^{\mathrm{new}}_{e^{\prime}}]\leq\bar{x}^{\mathrm{old}}_{e}\bar{x}^{\mathrm{old}}_{e^{\prime}}$.

###### Proof.

If the structure we found in the iteration is a cycle, then
$a_{e}=a_{e^{\prime}}=0$ and the equality holds trivially. So, we assume the
structure is a pseudo-marked-path $(i_{0},j_{1},i_{1},\cdots,j_{t},i_{t})$. If
at most one of $e$ and $e^{\prime}$ is on the path, then the lemma follows
from Claim 2.6. Consider the case $e$ and $e^{\prime}$ are both on the path.
This can only happen if $i_{0}=i_{t}=i$ and $e$ and $e^{\prime}$ are
$i_{0}j_{1}$ and $j_{t}i_{t}$. This holds as
$\operatorname*{\mathbb{E}}^{\prime}[\bar{x}^{\mathrm{new}}_{e}]=\bar{x}^{\mathrm{old}}_{e}$,
$\operatorname*{\mathbb{E}}^{\prime}[\bar{x}^{\mathrm{new}}_{e^{\prime}}]=\bar{x}^{\mathrm{old}}_{e^{\prime}}$,
and
$(\bar{x}^{\mathrm{new}}_{e}-\bar{x}^{\mathrm{old}}_{e})(\bar{x}^{\mathrm{new}}_{e^{\prime}}-\bar{x}^{\mathrm{old}}_{e^{\prime}})<0$
with probability 1. ∎

######  Lemma 2.9.

Let $i\in M$. If $|\delta^{k,\mathrm{mk}}_{i}\cap\bar{E}|\geq 2$ at the
beginning of the iteration, then we have
$\sum_{e\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}^{\mathrm{new}}_{e}p_{e}=\sum_{e\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}^{\mathrm{old}}_{e}p_{e}$.

###### Proof.

This follows from the second statement of Claim 2.5, and that
$\bar{x}^{\mathrm{new}}-\bar{x}^{\mathrm{old}}$ is $\theta a$ or
$-\theta^{\prime}a$. ∎

######  Lemma 2.10.

For a machine $i\in M$, an edge $e\in\delta^{k,\mathrm{umk}}_{i}$, we have

$\displaystyle{\textstyle\operatorname*{\mathbb{E}}^{\prime}}\Bigg{[}\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}^{\mathrm{new}}_{e}\bar{x}^{\mathrm{new}}_{e^{\prime}}p_{e^{\prime}}\Bigg{]}\leq\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}^{\mathrm{old}}_{e}\bar{x}^{\mathrm{old}}_{e^{\prime}}p_{e^{\prime}}.$

###### Proof.

If the structure we found in the iteration is a cycle, then $a_{e}=0$ as $e$
is unmarked. The lemma follows from Claim 2.6. So, we assume the structure we
found is a pseudo-marked-path.

By Lemma 2.9, if at the beginning of the iteration,
$|\delta^{k,\mathrm{mk}}_{i}\cap\bar{E}|\geq 2$, then
$\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}^{\mathrm{new}}_{e^{\prime}}p_{e^{\prime}}=\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}^{\mathrm{old}}_{e^{\prime}}p_{e^{\prime}}$
always holds.

$\displaystyle{\textstyle\operatorname*{\mathbb{E}}^{\prime}}\Bigg{[}\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}^{\mathrm{new}}_{e}\bar{x}^{\mathrm{new}}_{e^{\prime}}p_{e^{\prime}}\Bigg{]}$
$\displaystyle={\textstyle\operatorname*{\mathbb{E}}^{\prime}}\Bigg{[}\bar{x}^{\mathrm{new}}_{e}\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}^{\mathrm{new}}_{e^{\prime}}p_{e^{\prime}}\Bigg{]}={\textstyle\operatorname*{\mathbb{E}}^{\prime}}\Bigg{[}\bar{x}^{\mathrm{new}}_{e}\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}^{\mathrm{old}}_{e^{\prime}}p_{e^{\prime}}\Bigg{]}$
$\displaystyle={\textstyle\operatorname*{\mathbb{E}}^{\prime}}\Big{[}\bar{x}^{\mathrm{new}}_{e}\Big{]}\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}^{\mathrm{old}}_{e^{\prime}}p_{e^{\prime}}=\bar{x}^{{\mathrm{old}}}_{e}\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}^{\mathrm{old}}_{e^{\prime}}p_{e^{\prime}}.$

Then we consider the case $|\delta^{k,\mathrm{mk}}_{i}\cap\bar{E}|=1$; assume
the unique edge in $\delta^{k,\mathrm{mk}}_{i}\cap\bar{E}$ is $e^{\prime}$. If
at most one of $e$ and $e^{\prime}$ is on the pseudo-marked-path, the lemma
follows from Claim 2.6. If both of them are on the pseudo-marked-path, denoted
as $(i_{0},j_{1},i_{1},\cdots,j_{t},i_{t})$, then it must be the case that
$i_{0}=i_{t}$, and $e$ and $e^{\prime}$ are $i_{0}j_{1}$ and $j_{t}i_{t}$.
Then in the iteration, one of $a_{e}$ and $a_{e^{\prime}}$ is positive and the
other is negative. Then,
$\operatorname*{\mathbb{E}}^{\prime}[\bar{x}^{\mathrm{new}}_{e}\bar{x}^{\mathrm{new}}_{e^{\prime}}]\leq\bar{x}^{\mathrm{old}}_{e}\bar{x}^{\mathrm{old}}_{e^{\prime}}$,
which implies the lemma. ∎

By considering all iterations of Algorithm 2 and defining martingales (sub-
martingales) appropriately, we can prove the following corollary. Recall that
$\widehat{\operatorname*{\mathbb{E}}}[\cdot]=\operatorname*{\mathbb{E}}[\cdot|\beta]$.

######  Corollary 2.11.

Let $\bar{x}$ and $\bar{E}$ be the $\bar{x}$ and $\bar{E}$ at the end of
Algorithm 2. The following statements hold:

  1. (2.11a)

For every $e\in E^{k}$, we have
$\widehat{\operatorname*{\mathbb{E}}}[\bar{x}_{e}]=x_{e}$.

  2. (2.11b)

For every $j\in J_{k}$, we have
$\sum_{e\in\delta_{j}}\bar{x}_{e}=\sum_{e\in\delta_{j}}x_{e}=1$.

  3. (2.11c)

For a machine $i$ and two distinct edges
$e,e^{\prime}\in\delta^{k,\mathrm{umk}}_{i}$, we have
$\widehat{\operatorname*{\mathbb{E}}}[\bar{x}_{e}\bar{x}_{e^{\prime}}]\leq
x_{e}x_{e^{\prime}}$.

  4. (2.11d)

If $|\delta^{k,\mathrm{mk}}_{i}\cap\bar{E}|\geq 2$ for some $i\in M$, then
$\sum_{e\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}_{e}p_{e}=\sum_{e\in\delta^{k,\mathrm{mk}}_{i}}x_{e}p_{e}$.

  5. (2.11e)

For a machine $i\in M$, an edge $e\in\delta^{k,\mathrm{umk}}_{i}$, we have
$\widehat{\operatorname*{\mathbb{E}}}\big{[}\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}_{e}\bar{x}_{e^{\prime}}p_{e^{\prime}}\big{]}\leq\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}x_{e}x_{e^{\prime}}p_{e^{\prime}}$.

###### Proof.

The 5 statements respectively follow Claims 2.6, 2.7, and 2.8, and Lemmas 2.9
and 2.10. ∎

###  2.6 Algorithm 2 Returns an Integral Assignment

In this section we prove the following lemma, for a fixed job class $k$:

######  Lemma 2.12.

When Algorithm 2 terminates, we have $\bar{x}\in\\{0,1\\}^{E_{k}}$.

Combined with Property (2.11b), we have $\bar{x}$ gives an assignment of
$J_{k}$ to $M$. Our final assignment $\phi$ can be constructed by considering
all job classes $k$. This finishes the description of the whole algorithm.

###### Proof of Lemma 2.12.

When the algorithm terminates, we do not have a cycle of marked edges, or a
pseudo-marked-path in $\bar{E}$. So $(M,J_{k},E^{\mathrm{mk}}\cap\bar{E})$ is
a forest. We focus on a non-singleton tree $T$ of marked edges in the forest.
Let $J_{T}$ be the set of jobs in the tree $T$, and $M_{T}$ be the set of
machines. Notice that $J_{T}$ is incident to at most 1 unmarked edge in
$\bar{E}$: If there are two unmarked edges $ji$ and $j^{\prime}i^{\prime}$ in
$\bar{E}$ with $j,j^{\prime}\in J_{T}$, then we can take the path from $j$ to
$j^{\prime}$ in $T$, and concatenate it with $ij$ at the beginning and with
$j^{\prime}i^{\prime}$ at the end. This would give us a pseudo-marked-path.

First consider the case where there are no unmarked edges incident to $J_{T}$
in $\bar{G}$. Notice that $T$ contains at least 2 leaves. If it contains 2
leaf machines, then the path in $T$ between the two machines would be a
pseudo-marked-path. Otherwise, $T$ contains at least one leaf-job $j\in
J_{k}$. Assume $j$ is incident to $i\in M$ in $T$. If $i$ has degree at least
$2$ in $T$, then
$\sum_{e\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}_{e}p_{e}=\sum_{e\in\delta^{k,\mathrm{mk}}_{i}}x_{e}p_{e}=\mathrm{vol}(\delta^{k,\mathrm{mk}}_{i})\leq\beta\rho^{k}$
by Property (2.11d) and Claim 2.3. Notice that $p_{j}\geq\beta\rho^{k}$ and
$ij$ is the only edge incident to $j$ in $\bar{E}$, which implies
$\bar{x}_{ij}=1$. This contradicts that $i$ has degree at least 2 in $T$. So
$i$ has degree 1 in $T$ and $T$ consists of the single edge $ij$ with
$x_{ij}=1$.

Consider the second case where there is exactly one unmarked edge incident to
$J_{T}$ in $\bar{G}$. Assume the edge is $e$ and it is incident to $j\in
J_{T}$. If there is one leaf machine in $T$, then concatenating the path
between the leaf machine and $j$ in $T$ and $e$ would give us a pseudo-marked-
path. So $T$ does not have a leaf machine, and this implies
$|J_{T}|\geq|M_{T}|+1$. Then again by Property (2.11d) and Claim 2.3 we have
$\sum_{e\in\delta^{k,\mathrm{mk}}_{i}}\bar{x}_{e}p_{e}\leq\beta\rho^{k}$ for
every machine $i\in M_{T}$. Every job in $J_{T}$ has size at least
$\beta\rho^{k}$, and $J_{T}$ is incident to only 1 unmarked edge. This can
only happen if $T$ is the singleton $(\\{j\\},\emptyset)$.

So, all the marked edges $e\in E_{k}$ have $\bar{x}_{e}\in\\{0,1\\}$. As every
$j\in J_{k}$ can be incident to at most 1 unmarked edge in $\bar{E}$ in the
end, all the unmarked edges $e\in E^{k}$ also have $\bar{x}_{e}\in\\{0,1\\}$.
∎

######  Lemma 2.13.

For two distinct edges $e,e^{\prime}\in\delta^{i,\mathrm{mk}}_{k}$, we have
$\bar{x}_{e}\bar{x}_{e^{\prime}}=0$ at the end of the algorithm.

###### Proof.

By Lemma 2.6 we have $\bar{x}_{e}\in\\{0,1\\}$ and
$\bar{x}_{e^{\prime}}\in\\{0,1\\}$ at the end of the algorithm. Assume towards
the contradiction that $\bar{x}_{e}=1$ and $\bar{x}_{e^{\prime}}=1$ can happen
with positive probability. Then by Property (2.11d) and Claim 2.3, we have
$\sum_{e^{\prime\prime}\in\delta^{i,\mathrm{mk}}_{k}}\bar{x}_{e^{\prime\prime}}p_{e^{\prime\prime}}=\sum_{e^{\prime\prime}\in\delta^{i,\mathrm{mk}}_{k}}x_{e^{\prime\prime}}p_{e^{\prime\prime}}\leq\beta\rho^{k}$.
This contradicts that
$\bar{x}_{e}=1,\bar{x}_{e^{\prime}}=1,p_{e}\geq\beta\rho^{k}$ and
$p_{e^{\prime}}\geq\beta\rho^{k}$. ∎

##  3 An Upper Bound on Weighted Completion Time on Machine $i$

In this section we fix a machine $i$, rewrite the LP cost on $i$, and prove an
upper bound on the expected weighted completion time on $i$ in our solution.
Then in Section 4, we analyze the ratio between the two quantities. As the
edges $E$ and the vector $x\in(0,1]^{E}$ depend on the random choice $\beta$,
in Section 4 it will be more convenient to express the formulations using jobs
$J$ and the $z$-vector. So, we define $\sigma_{j}:=\frac{w_{ij}}{p_{j}}$ to be
the Smith ratio of $j$ on machine $i$ for every $j\in J$. We index $j$ as
$[n]$ so that $\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{n}$. Define
$\sigma_{n+1}=0$ for convenience.

We first rewrite the LP cost on $i$:

######  Lemma 3.1.

We have

$\displaystyle\sum_{f}y_{if}\cdot\mathrm{cost}_{i}(f)=\sum_{j^{*}\in[n]}(\sigma_{j^{*}}-\sigma_{j^{*}+1})\cdot\frac{1}{2}\left(\sum_{j\in[j^{*}]}z_{ij}p_{j}^{2}+\sum_{f}y_{if}\cdot
p^{2}(f\cap[j^{*}])\right).$ (5)

###### Proof.

The left side of the equality is

$\displaystyle\quad\sum_{f}y_{if}\sum_{j^{\prime},j\in f:j^{\prime}\leq
j}\sigma_{j}p_{j}p_{j^{\prime}}=\sum_{f}y_{if}\sum_{j^{\prime},j\in
f,j^{*}\in[n]:j^{\prime}\leq j\leq
j^{*}}(\sigma_{j^{*}}-\sigma_{j^{*}+1})p_{j}p_{j^{\prime}}$
$\displaystyle=\sum_{j^{*}\in[n]}(\sigma_{j^{*}}-\sigma_{j^{*}+1})\sum_{f}y_{if}\sum_{j^{\prime}\leq
j\leq j^{*}:j^{\prime},j\in f}p_{j}p_{j^{\prime}}$
$\displaystyle=\sum_{j^{*}\in[n]}(\sigma_{j^{*}}-\sigma_{j^{*}+1})\sum_{f}y_{if}\cdot\frac{1}{2}\left(\sum_{j\in
f\cap[j^{*}]}p_{j}^{2}+\Big{(}\sum_{j\in f\cap[j^{*}]}p_{j}\Big{)}^{2}\right)$
$\displaystyle=\sum_{j^{*}\in[n]}(\sigma_{j^{*}}-\sigma_{j^{*}+1})\cdot\frac{1}{2}\left(\sum_{j\in[j^{*}]}z_{ij}p_{j}^{2}+\sum_{f}y_{if}\cdot
p^{2}(f\cap[j^{*}])\right).$

The last inequality used $\sum_{f\ni j}y_{if}=z_{ij}$ for every $j\in[n]$. ∎

Till the end of the section, we fix the random choice $\beta\in[1,\rho)$. Let
${\mathrm{wC}}^{(i)}$ denote total weighted completion time of jobs assigned
to $i$, in the solution produced by our algorithm. Recall that
$\widehat{\operatorname*{\mathbb{E}}}[\cdot]$ is
$\operatorname*{\mathbb{E}}[\cdot|\beta]$. For a job $j\in[n]$, define
$\mathrm{vol}(j):=z_{ij}p_{j}$. This is equal to $\sum_{e=ij}\mathrm{vol}(e)$.
For a set $J^{\prime}\subseteq[n]$ of jobs, define
$\mathrm{vol}(J^{\prime})=\sum_{j\in J^{\prime}}\mathrm{vol}(j)$. The main
goal of this section is to prove the following lemma, that bounds the cost on
$i$ in our solution:

######  Lemma 3.2.

The expected weighted completion time on machine $i$ conditioned on $\beta$ is

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}[{\mathrm{wC}}^{(i)}]\leq\sum_{j^{*}=1}^{n}(\sigma_{j^{*}}-\sigma_{j^{*}+1})\Bigg{(}\sum_{j\in[j^{*}]}z_{ij}p_{j}^{2}+\frac{1}{2}\cdot\mathrm{vol}^{2}([j^{*}])-\frac{1}{2}\sum_{k}\Big{(}\min\Big{\\{}\mathrm{vol}([j^{*}]\cap
J_{k}),\beta\rho^{k}\Big{\\}}\Big{)}^{2}\Bigg{)}.$ (6)

###### Proof.

In the proof, we use edges and $x$-vector instead of jobs and $z$-vector.
Recall that $\sigma_{e}=\frac{w_{ij}}{p_{j}}$ if $e$ is an edge between $i$
and $j$. We define a total order $\prec$ over the set $\delta_{i}$ of incident
of edges of $i$ in $G$ using their order of creation in Algorithm 1: $e\prec
e^{\prime}$ if $e$ is created before $e^{\prime}$; this implies
$\sigma_{e}\geq\sigma_{e^{\prime}}$. In particular, for any two parallel edges
$e$ and $e^{\prime}$ with $e$ marked and $e^{\prime}$ unmarked, we have
$e\prec e^{\prime}$. We define $e\preceq e^{\prime}$ if $e\prec e^{\prime}$ or
$e=e^{\prime}$. For every $e\in\delta^{i}$, we define $\mathrm{next}(e)$ to be
the edge after $e$ in the order $\prec$. For the last edge $e$ in the order,
we define $\sigma_{\mathrm{next}(e)}=0$ for convenience. We use
$[e]:=\\{e^{\prime}\in\delta_{i}:e^{\prime}\preceq e\\}$ to denote the set of
edges before $e$ in the order $\prec$, including the edge $e$ itself.

With the notations defined, (6) becomes

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\big{[}{\mathrm{wC}}^{(i)}\big{]}\leq\sum_{e^{*}\in\delta_{i}}(\sigma_{e^{*}}-\sigma_{\mathrm{next}(e^{*})})\Big{(}\sum_{e\preceq
e^{*}}x_{e}p_{e}^{2}+\frac{1}{2}\cdot\mathrm{vol}^{2}([e^{*}])-\frac{1}{2}\sum_{k}\big{(}\min\big{\\{}\mathrm{vol}([e^{*}]\cap\delta^{i}_{k}),\beta\rho^{k}\big{\\}}\big{)}^{2}\Big{)}.$
(7)

To see the equivalence of the two inequalities, we make two modifications to
the right side (7). First, merging two parallel edges $e$ and $e^{\prime}$
into a new edge $e^{\prime\prime}$ with
$x_{e^{\prime\prime}}=x_{e}+x_{e^{\prime}}$ does not change the quantity. ($e$
and $e^{\prime}$ are next to each other in the order $\prec$, and thus the new
order can be naturally defined.) This holds as
$\sigma_{e}=\sigma_{e^{\prime}},p_{e}=p_{e^{\prime}}$. Then for any
$j^{*}\in[n]$ with no edges between $i$ and $j$ in $G$, we add an dummy edge
$e=ij$ of $p_{e}=p_{J},\sigma_{e}=\frac{w_{ij}}{p_{j}},x_{e}=0$, and insert it
into the order $\prec$ naturally. The operation does not change (7). After the
two operations, the right side of (7) becomes (6). So now we focus on the
proof of (7).

For every $k$ and every $e\in\delta^{i}_{k}$, we define $X_{e}$ to be the
final value of $\bar{x}_{e}$ in Algorithm 2 for the job class $k$. By Lemma
2.12, $X_{e}\in\\{0,1\\}$. The total weighted completion time of jobs on
machine $i$ is

$\displaystyle{\mathrm{wC}}^{(i)}$
$\displaystyle=\sum_{e\in\delta_{i}}X_{e}\sigma_{e}p_{e}\sum_{e^{\prime}\preceq
e}X_{e^{\prime}}p_{e^{\prime}}=\sum_{e\in\delta_{i}}X_{e}p_{e}\sum_{e^{*}\succeq
e}(\sigma_{e^{*}}-\sigma_{\mathrm{next}(e^{*})})\sum_{e^{\prime}\preceq
e}X_{e^{\prime}}p_{e^{\prime}}$
$\displaystyle=\sum_{e^{*}\in\delta_{i}}(\sigma_{e^{*}}-\sigma_{\mathrm{next}(e^{*})})\sum_{e^{\prime}\preceq
e\preceq
e^{*}}X_{e}X_{e^{\prime}}p_{e}p_{e^{\prime}}=\sum_{e^{*}\in\delta_{i}}(\sigma_{e^{*}}-\sigma_{\mathrm{next}(e^{*})})\left(\sum_{e\preceq
e^{*}}X_{e}p_{e}^{2}+\sum_{e^{\prime}\prec e\preceq
e^{*}}X_{e}X_{e^{\prime}}p_{e}p_{e^{\prime}}\right).$ (8)

The last equality used that $X_{e}\in\\{0,1\\}$, which implies
$X_{e}^{2}=X_{e}$, for every $e\in\delta_{i}$. We fix an $e^{*}\in\delta_{i}$
and upper bound
$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\Big{[}\sum_{e^{\prime}\prec
e\preceq e^{*}}X_{e}X_{e^{\prime}}p_{e}p_{e^{\prime}}\Big{]}$.

Focus on two edges $e^{\prime}$ and $e$ with $e^{\prime}\prec e\preceq e^{*}$.
First, if $e\in\delta^{k}_{i}$ and $e^{\prime}\in\delta^{k^{\prime}}_{i}$ for
some $k\neq k^{\prime}$, then we have
$\widehat{\operatorname*{\mathbb{E}}}[X_{e}X_{e^{\prime}}]=\widehat{\operatorname*{\mathbb{E}}}[X_{e}]\widehat{\operatorname*{\mathbb{E}}}[X_{e^{\prime}}]=x_{e}x_{e^{\prime}}$
as Algorithm 2 for job classes $k$ and $k^{\prime}$ are independent. So we
assume $e^{\prime}$ and $e$ are both in $\delta^{k}_{i}$ for some $k$. If $e$
is marked, so is $e^{\prime}$. By Lemma 2.13, $X_{e}X_{e^{\prime}}=0$ always
happens conditioned on the given $\beta$. If both $e$ and $e^{\prime}$ are
unmarked, we have
$\widehat{\operatorname*{\mathbb{E}}}[X_{e}X_{e^{\prime}}]\leq
x_{e}x_{e^{\prime}}$ by Property (2.11c).

For an edge $e\in[e^{*}]\cap\delta^{k,\mathrm{umk}}_{i}$, we have
$\widehat{\operatorname*{\mathbb{E}}}\big{[}\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}X_{e}X_{e^{\prime}}p_{e^{\prime}}\big{]}\leq\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}x_{e}x_{e^{\prime}}p_{e^{\prime}}$
by Property (2.11e). Notice that $e^{\prime}\prec e$ for every
$e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}$. So, for an edge
$e\in[e^{*}]\cap\delta^{k,\mathrm{umk}}_{i}$, we have

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\Bigg{[}\sum_{e^{\prime}\prec
e}X_{e}X_{e^{\prime}}p_{e}p_{e^{\prime}}\Bigg{]}$
$\displaystyle=\widehat{\operatorname*{\mathbb{E}}}\Bigg{[}\sum_{e^{\prime}\in[e]\setminus\delta^{k}_{i}}X_{e}X_{e^{\prime}}p_{e}p_{e^{\prime}}\Bigg{]}+\widehat{\operatorname*{\mathbb{E}}}\Bigg{[}\sum_{e^{\prime}\prec
e:e^{\prime}\in\delta^{k,\mathrm{umk}}_{i}}X_{e}X_{e^{\prime}}p_{e}p_{e^{\prime}}\Bigg{]}+\widehat{\operatorname*{\mathbb{E}}}\Bigg{[}\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}X_{e}X_{e^{\prime}}p_{e}p_{e^{\prime}}\Bigg{]}$
$\displaystyle\leq\sum_{e^{\prime}\in[e]\setminus\delta^{k}_{i}}x_{e}x_{e^{\prime}}p_{e}p_{e^{\prime}}+\sum_{e^{\prime}\prec
e:e^{\prime}\in\delta^{k,\mathrm{umk}}_{i}}x_{e}x_{e^{\prime}}p_{e}p_{e^{\prime}}+\sum_{e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}x_{e}x_{e^{\prime}}p_{e}p_{e^{\prime}}$
$\displaystyle=\sum_{e^{\prime}\prec
e}x_{e}x_{e^{\prime}}p_{e}p_{e^{\prime}}.$

For an edge $e\in[e^{*}]\cap\delta^{k,\mathrm{mk}}_{i}$, we have

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\Bigg{[}\sum_{e^{\prime}\prec
e}X_{e}X_{e^{\prime}}p_{e}p_{e^{\prime}}\Bigg{]}$
$\displaystyle=\widehat{\operatorname*{\mathbb{E}}}\Bigg{[}\sum_{e^{\prime}\in[e]\setminus\delta^{k}_{i}}X_{e}X_{e^{\prime}}p_{e}p_{e^{\prime}}\Bigg{]}=\sum_{e^{\prime}\in[e]\setminus\delta^{k}_{i}}x_{e}x_{e^{\prime}}p_{e}p_{e^{\prime}}=\sum_{e^{\prime}\prec
e}x_{e}x_{e^{\prime}}p_{e}p_{e^{\prime}}-\sum_{e^{\prime}\prec
e:e^{\prime}\in\delta^{k}_{i}}x_{e}x_{e^{\prime}}p_{e}p_{e^{\prime}}.$

Therefore, for a fixed $e^{*}\in\delta_{i}$, we have:

$\displaystyle\quad\widehat{\operatorname*{\mathbb{E}}}\Bigg{[}\sum_{e^{\prime}\prec
e\preceq
e^{*}}X_{e}X_{e^{\prime}}p_{e}p_{e^{\prime}}\Bigg{]}\leq\sum_{e^{\prime}\prec
e\preceq
e^{*}}x_{e}x_{e^{\prime}}p_{e}p_{e^{\prime}}-\sum_{k}\sum_{e^{\prime}\prec
e\preceq
e^{*}:e,e^{\prime}\in\delta^{k,\mathrm{mk}}_{i}}x_{e}x_{e^{\prime}}p_{e}p_{e^{\prime}}$
$\displaystyle=\frac{1}{2}\Big{(}\sum_{e\in[e^{*}]}x_{e}p_{e}\Big{)}^{2}-\frac{1}{2}\sum_{e\in[e^{*}]}x_{e}^{2}p_{e}^{2}-\sum_{k}\left(\frac{1}{2}\Big{(}\sum_{e\in[e^{*}]\cap\delta^{k,\mathrm{mk}}_{i}}x_{e}p_{e}\Big{)}^{2}-\frac{1}{2}\sum_{e\in[e^{*}]\cap\delta^{k,\mathrm{mk}}_{i}}x_{e}^{2}p_{e}^{2}\right)$
$\displaystyle\leq\frac{1}{2}\Big{(}\sum_{e\in[e^{*}]}x_{e}p_{e}\Big{)}^{2}-\frac{1}{2}\sum_{k}\Big{(}\sum_{e\in[e^{*}]\cap\delta^{k,\mathrm{mk}}_{i}}x_{e}p_{e}\Big{)}^{2}=\frac{1}{2}\cdot\mathrm{vol}^{2}([e^{*}])-\frac{1}{2}\sum_{k}\Big{(}\min\Big{\\{}\mathrm{vol}\big{(}[e^{*}]\cap\delta^{k}_{i}\big{)},\beta\rho^{k}\Big{\\}}\Big{)}^{2}.$

The last equality follows from that we mark the first $\beta\rho^{k}$ volume
of edges in $\sigma^{k}_{i}$ in Algorithm 1 according to the order $\prec$.

Combining the inequality, (8) and that
$\widehat{\operatorname*{\mathbb{E}}}\big{[}\sum_{e\preceq
e^{*}}X_{e}p_{e}^{2}\big{]}=\sum_{e\preceq e^{*}}x_{e}p_{e}^{2}$, we have

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}[{\mathrm{wC}}^{(i)}]\leq\sum_{e^{*}\in\delta_{i}}(\sigma_{e^{*}}-\sigma_{\mathrm{next}(e^{*})})\Bigg{(}\sum_{e\preceq
e^{*}}x_{e}p_{e}^{2}+\frac{1}{2}\cdot\mathrm{vol}^{2}([e^{*}])-\frac{1}{2}\sum_{k}\big{(}\min\big{\\{}\mathrm{vol}([e^{*}]\cap\delta^{k}_{i}),\beta\rho^{k}\big{\\}}\big{)}^{2}\Bigg{)},$

which is precisely (7). ∎

##  4 Analyzing Approximation Ratio with Computer Assistance

In this section, we prove the $1.36$-approximation ratio of our algorithm for
a fixed machine $i\in M$, by comparing the right side of (5) and the
expectation of the right side of (6) over all random choices of $\beta$.
Specifically, we fix $j^{*}$, and compare the term after
$(\sigma_{j^{*}}-\sigma_{j^{*}+1})$ in (5), and the counterpart in (6).

Therefore, we only consider jobs in $[j^{*}]$ in this section. We restrict all
the configurations on $i$ to be subsets of $[j^{*}]$. With a slight abuse of
notations, we still use $y_{if}$ values to denote the masses of the
configurations, after restricting jobs to $[j^{*}]$. That is, for any
$f\subseteq[j^{*}]$, the new $y_{if}$ value equals the old
$\sum_{f^{\prime}\cap[j^{*}]=f}y_{if^{\prime}}$. Now we set $\rho=2$ and our
analysis in this section is tailored to this value of $\rho$. The main lemma
we prove in this section is:

######  Lemma 4.1.

We have

$\displaystyle\qquad{\operatorname*{\mathbb{E}}}_{\beta}\left[\sum_{j\in[j^{*}]}z_{ij}p_{j}^{2}+\frac{1}{2}\cdot\mathrm{vol}^{2}([j^{*}])-\frac{1}{2}\sum_{k}\Big{(}\min\Big{\\{}\mathrm{vol}([j^{*}]\cap
J_{k}),\beta\cdot 2^{k}\Big{\\}}\Big{)}^{2}\right]$ $\displaystyle\leq
1.36\times\frac{1}{2}\Big{(}\sum_{j\in[j^{*}]}z_{ij}p_{j}^{2}+\sum_{f}y_{if}\cdot
p^{2}(f)\Big{)}.$

Combine the lemma with Lemma 3.1 and 3.2, we have that the expected weighted
completion time of jobs assigned to $i$ is at most $1.36$ times the cost of
$i$ in the LP solution. This leads to our $1.36$-approximation ratio,
finishing the proof of Theorem 1.1.

#### Notations

For a fixed $\beta$, define $t:=\beta\cdot 2^{k}$ for the biggest integer $k$
such that $\beta\cdot 2^{k}\leq\frac{\mathrm{vol}([j^{*}])}{2}$. Therefore,
$\frac{\mathrm{vol}([j^{*}])}{t}\in[2,4)$. We let $q_{j}=\frac{p_{j}}{t}$ for
every $j\in[j^{*}]$ be a scaled processing time of $j$. Similarly, define
$q(J^{\prime})=\sum_{j\in J^{\prime}}q_{j}$ for every
$J^{\prime}\subseteq[j^{*}]$. We define

$\displaystyle v_{k}(f):=\sum_{j\in f:2^{k}\leq
q_{j}<2^{k+1}}q_{j},\quad\text{for any configuration }f\subseteq[j^{*}]\text{
and integer }k,$ $\displaystyle L$
$\displaystyle:=\frac{\mathrm{vol}([j^{*}])}{t}=\sum_{j\in[j^{*}]}z_{ij}q_{j}=\sum_{f}y_{if}q(f)\in[2,4),$
$\displaystyle Q:=\sum_{j\in[j^{*}]}z_{ij}q_{j}^{2}=\sum_{f}y_{if}\sum_{j\in
f}q_{j}^{2},$ $\displaystyle F$ $\displaystyle:=\sum_{f}y_{if}\cdot q^{2}(f),$
$\displaystyle S:=\sum_{k}\Big{(}\min\Big{\\{}\sum_{f}y_{if}\cdot
v_{k}(f),2^{k}\Big{\\}}\Big{)}^{2}.$

Notice that all the definitions depend on $\beta$, and thus are random. In
particular, $\ln\frac{L}{2}$ is also uniformly distributed in $[0,\ln 2)$.

With the notations defined, we proceed to the proof of Lemma 4.1. Our goal is
to define a constant $\alpha_{L}\in[1,1.5]$ for every $L\in[2,4)$ so that

$\displaystyle Q+\frac{1}{2}\cdot L^{2}-\frac{1}{2}\cdot S$
$\displaystyle\leq\alpha_{L}\cdot\frac{1}{2}\Big{(}Q+F\Big{)},\text{for every
}\beta\in[0,\ln 2),\text{and}$ (9)
$\displaystyle{\operatorname*{\mathbb{E}}}_{\beta}\big{[}\alpha_{L}\big{]}$
$\displaystyle\leq 1.36.$ (10)

Multiplying both sides of (9) by $t^{2}$, and taking the expectation of both
sides over $\beta$, we obtain the inequality in Lemma 4.1. To see this, notice
that $Q\cdot t^{2}=\sum_{j\in[j^{*}]}z_{ij}p_{j}^{2},L^{2}\cdot
t^{2}=\mathrm{vol}^{2}([j^{*}])$ and $F\cdot t^{2}=\sum_{f}y_{if}\cdot
p^{2}(f)$. Letting $k^{\prime}$ be the integer such that $t=\beta\cdot
2^{k^{\prime}}$, we have

$\displaystyle S\cdot t^{2}$
$\displaystyle=\sum_{k}\Big{(}\min\Big{\\{}\sum_{f}y_{if}\cdot v_{k}(f)\cdot
t,\beta\cdot
2^{k+k^{\prime}}\Big{\\}}\Big{)}^{2}=\sum_{k^{\prime\prime}}\Big{(}\min\Big{\\{}\mathrm{vol}([j^{*}]\cap
J_{k^{\prime\prime}}),\beta\cdot 2^{k^{\prime\prime}}\Big{\\}}\Big{)}^{2}.$

The second inequality follows by defining $k^{\prime\prime}=k+k^{\prime}$.
Also a job $j\in f$ is counted towards $v_{k}(f)$ if and only if $j\in
J_{k^{\prime\prime}}$, and when it is counted, we have $q_{j}\cdot t=p_{j}$.

Therefore, it remains to set $\alpha_{L}$ values so that (9) and (10) hold. If
we set $\alpha_{L}=1.5$ for every $L$, then (9) holds even without the
$\frac{1}{2}\cdot S$ term on the left-side, as $Q\leq F$ and $L^{2}\leq F$. So
we can always set $\alpha_{L}\leq 1.5$.

#### Capturing $\alpha_{L}$ using a Mathematical Program

Till the end of the section, we fix the random variable $\beta$, and thus $L$.
We define a size-configuration to be a multi-set $g\subseteq{\mathbb{R}}_{\geq
0}$ of positive reals with $|g|\leq n$. As the name suggests, a size-
configuration is obtained from a configuration by replacing each job with its
size. For every size configuration $g$, we define $v_{0}(g),v_{1}(g)$ and
$v_{2}(g)$ to be the sum of elements of $g$ in $[1,2),[2,4)$ and $[4,8)$
respectively. This corresponds to the definition of $v_{k}(f)$ for
configurations $f$; but we only need to define $v_{0}(g),v_{1}(g)$ and
$v_{2}(g)$ for size-configurations $g$.

Let $\alpha\in[1,1.5]$ be fixed; this will be our target value for
$\alpha_{L}$. Now we introduce a program which aims to check if
$\alpha_{L}=\alpha$ is satisfies (9). In the program, we have a variable
$y^{\prime}_{g}$ for every size-configuration $g$, and three variables
$V_{0},V_{1}$ and $V_{2}$. The program is defined by the objective (11), and
constraints (12-15).222Notice the program has uncountable many variables, but
(12) and (13) will require there are countably many variables with non-zero
values.

$\max\qquad\sum_{g}y^{\prime}_{g}\Big{(}\big{(}1-\frac{\alpha}{2}\big{)}\sum_{a\in
g}a^{2}-\frac{\alpha}{2}\big{(}\sum
g\big{)}^{2}\Big{)}+\frac{1}{2}L^{2}-\frac{1}{2}\big{(}(\min(V_{0},1))^{2}+(\min(V_{1},2))^{2}+V_{2}^{2}\big{)}$
(11)

$\displaystyle\sum_{g}y^{\prime}_{g}$ $\displaystyle=1$ (12) $\displaystyle
y^{\prime}_{g}$ $\displaystyle\geq 0$ $\displaystyle\forall g$ (13)

$\displaystyle\sum_{g}y^{\prime}_{g}\cdot(\sum g)$ $\displaystyle=L$ (14)
$\displaystyle\sum_{g}y^{\prime}_{g}v_{k}(g)-V_{k}$ $\displaystyle=0$
$\displaystyle\forall k\in\\{0,1,2\\}$ (15)

In the program, $y^{\prime}_{g}$ is the fraction of $g$ we choose. (12)
requires that we choose in total 1 fraction of size-configuration, (13) is the
non-negativity condition. (14) gives the definition of $L$. $V_{0},V_{1}$ and
$V_{2}$ are the total “volume” of elements in $[1,2),[2,4)$ and $[4,8)$
respectively; this gives us (15). Notice that (9) is equivalent to
$\displaystyle\Big{(}1-\frac{\alpha_{L}}{2}\Big{)}Q-\frac{\alpha_{L}}{2}\cdot
F+\frac{1}{2}\cdot L^{2}-\frac{1}{2}\cdot S\leq 0$. This gives us the
objective (11).

######  Lemma 4.2.

If for some $\alpha\in[1,1.5]$, program (11) has value at most $0$, then (9)
is satisfied with $\alpha_{L}=\alpha$.

###### Proof.

Consider the $y_{if}$ values for the configurations $f$. We can covert the
configurations to size configurations naturally: Start from $y^{\prime}_{g}=0$
for every size-configuration $g$. For every configuration $f$ with $y_{if}>0$,
we let $g=\\{q_{j}:j\in f\\}$ be its correspondent size-configuration ($g$ is
a multi-set). Then we increase $y^{\prime}_{g}$ by $y_{if}$. Let
$V_{k}=\sum_{g}y^{\prime}_{g}v_{k}(g)$ for every $k\in\\{0,1,2\\}$. Clearly,
$(y^{\prime},V_{0},V_{1},V_{2})$ satisfy all the constraints in the program.
So the value of (11) on this $(y^{\prime},V_{0},V_{1},V_{2})$ is at most $0$.
Then,

$\displaystyle\quad\Big{(}1-\frac{\alpha}{2}\Big{)}Q-\frac{\alpha}{2}\cdot
F+\frac{1}{2}\cdot L^{2}-\frac{1}{2}\cdot S$
$\displaystyle=\sum_{f\subseteq[j^{*}]}y_{if}\left(\big{(}1-\frac{\alpha}{2}\big{)}\sum_{j\in
f}q_{j}^{2}-\frac{\alpha}{2}\cdot
q^{2}(f)+\frac{1}{2}L^{2}\right)-\frac{1}{2}\sum_{k}\Big{(}\min\Big{\\{}\sum_{f}y_{if}\cdot
v_{k}(f),2^{k}\Big{\\}}\Big{)}^{2}$
$\displaystyle\leq\sum_{g}y^{\prime}_{g}\left(\big{(}1-\frac{\alpha}{2}\big{)}\sum_{a\in
g}a^{2}-\frac{\alpha}{2}\cdot\big{(}\sum
g\big{)}^{2}+\frac{1}{2}L^{2}\right)-\frac{1}{2}\sum_{k=0}^{2}\Big{(}\min\Big{\\{}\sum_{g}y^{\prime}_{g}\cdot
v_{k}(g),2^{k}\Big{\\}}\Big{)}^{2}$
$\displaystyle\leq\sum_{g}y^{\prime}_{g}\left(\big{(}1-\frac{\alpha}{2}\big{)}\sum_{a\in
g}a^{2}-\frac{\alpha}{2}\cdot\big{(}\sum
g\big{)}^{2}+\frac{1}{2}L^{2}\right)-\frac{1}{2}\big{(}(\min(V_{0},1))^{2}+(\min(V_{1},2))^{2}+V_{2}^{2}\big{)}\leq
0.$

Notice that
$V_{2}\leq\sum_{f}y^{\prime}_{g}v_{2}(f)\leq\sum_{f}y^{\prime}_{g}q(f)=L<4$
and thus $\min(V_{2},4)=V_{2}$. The inequality is equivalent to
$Q+\frac{1}{2}L^{2}-\frac{1}{2}S\leq\alpha\cdot\frac{1}{2}(Q+F)$; so setting
$\alpha_{L}=\alpha$ will satisfy (9). ∎

Next, we show that we only need to consider the size-configurations $g$
satisfying certain property:

######  Lemma 4.3.

In program (11), we can w.l.o.g assume $y^{\prime}_{g}=0$ for any size-
configuration $g$ with $\big{(}\sum g\big{)}-(\min g)\geq L$.

###### Proof.

If $y^{\prime}_{g}>0$ for such a size-configuration $g$. We let $a=\min g$, we
can then remove $a$ from $g$, and add the $y^{\prime}_{g}$ fraction of $a$ to
$y^{\prime}_{g}$ fractional size-configurations $g^{\prime}$ with $(\sum
g^{\prime})<L$. This can be done as $\sum_{g}y^{\prime}_{g}\sum_{a\in g}a=L$.
This operation does not change $V_{0},V_{1}$ and $V_{2}$, and
$\sum_{g}y^{\prime}_{g}\sum_{a\in g}a^{2}$, and it will decrease
$\sum_{f}y^{\prime}_{g}(\sum g)^{2}$. Therefore, it will increase the value of
the objective. ∎

Program (11) is not a convex program, due to the terms $(\min(V_{0},1))^{2}$
and $(\min(V_{1},2))^{2}$. Therefore, we break the program into 3 sub-
programs, each of which is a convex one. They all have the same set of
constraints (12-15). The objectives of the 3 sub-programs are respectively

$\displaystyle\max\quad\sum_{g}y^{\prime}_{g}\Big{(}\big{(}1-\frac{\alpha}{2}\big{)}\sum_{a\in
g}a^{2}-\frac{\alpha}{2}\big{(}\sum
g\big{)}^{2}\Big{)}+\frac{1}{2}L^{2}-\frac{1}{2}\cdot 2^{2},$ (16)
$\displaystyle\max\quad\sum_{g}y^{\prime}_{g}\Big{(}\big{(}1-\frac{\alpha}{2}\big{)}\sum_{a\in
g}a^{2}-\frac{\alpha}{2}\big{(}\sum
g\big{)}^{2}\Big{)}+\frac{1}{2}L^{2}-\frac{1}{2}\big{(}1^{2}+V_{1}^{2}+V_{2}^{2}\big{)},$
(17)
$\displaystyle\max\quad\sum_{g}y^{\prime}_{g}\Big{(}\big{(}1-\frac{\alpha}{2}\big{)}\sum_{a\in
g}a^{2}-\frac{\alpha}{2}\big{(}\sum
g\big{)}^{2}\Big{)}+\frac{1}{2}L^{2}-\frac{1}{2}\big{(}V_{0}^{2}+V_{1}^{2}+V_{2}^{2}\big{)}.$
(18)

Notice we do not need to add constraints $V_{1}\leq 2$ or $V_{1}\geq 2$ to the
sub-programs.

######  Lemma 4.4.

If for some $\alpha\in[1,1.5]$, the values of the three sub-programs (16),
(17) and (18) are non-positive, so is the value of program (11).

###### Proof.

We consider the contra-positive of the statement: We assume the value of
program (11) is positive, and prove that one of the three sub-programs have
positive value. Consider a solution $(y^{\prime},V_{0},V_{1},V_{2})$ to the
program (11) that gives the positive value. If $V_{1}\geq 2$, then the
objective (16) is positive. If $V_{1}<2$ and $V_{0}\geq 1$, then the objective
becomes (17), and thus it is positive. Finally, if $V_{1}<2$ and $V_{0}<1$,
the objective (18) is positive. ∎

Thus our goal is now to set $\alpha_{L}$ values, so that the three sub-
programs have non-positive values.

#### Analysis of Sub-Program (16).

First we consider sub-program (16). For any feasible solution
$(y^{\prime},V_{0},V_{1},V_{2})$, the objective of the program is

$\displaystyle\quad\sum_{f}y^{\prime}_{g}\Big{(}\big{(}1-\frac{\alpha}{2}\big{)}\sum_{a\in
g}a^{2}-\frac{\alpha}{2}\big{(}\sum
g\big{)}^{2}\Big{)}+\frac{1}{2}L^{2}-\frac{1}{2}\cdot 2^{2}$
$\displaystyle\leq-\sum_{g}y^{\prime}_{g}\cdot(\alpha-1)\big{(}\sum
g\big{)}^{2}+\frac{1}{2}L^{2}-2\leq-(\alpha-1)L^{2}+\frac{1}{2}L^{2}-2=\Big{(}\frac{3}{2}-\alpha\Big{)}L^{2}-2.$

We used that $\sum_{a\in g}a^{2}\leq\big{(}\sum g\big{)}^{2}$ and
$L=\sum_{g}(\sum g)$. So, for $\alpha=\frac{3}{2}-\frac{2}{L^{2}}$, the value
of the sub-program is non-positive.

#### Analysis of Sub-Program (17).

Now, we consider sub-program (17). As the objective does not contain $V_{0}$,
constraint (15) for $k=0$ becomes redundant. Using Lagrangian multipliers, the
value of the sub-program is at most

$\displaystyle\inf_{\mu,\lambda_{1},\lambda_{2}\in{\mathbb{R}}_{\geq
0}}\quad\sup_{y^{\prime},V_{1},V_{2}}\qquad$
$\displaystyle\sum_{f}y^{\prime}_{g}\Big{(}\big{(}1-\frac{\alpha}{2}\big{)}\sum_{a\in
g}a^{2}-\frac{\alpha}{2}\big{(}\sum
g\big{)}^{2}\Big{)}+\frac{1}{2}L^{2}-\frac{1}{2}\big{(}1+V_{1}^{2}+V_{2}^{2}\big{)}$
$\displaystyle+\mu\big{(}\sum_{g}y^{\prime}_{g}\big{(}\sum
g\big{)}-L\big{)}-\lambda_{1}\big{(}\sum_{g}y^{\prime}_{g}v_{1}(g)-V_{1}\big{)}-\lambda_{2}\big{(}\sum_{g}y^{\prime}_{g}v_{2}(g)-V_{2}\big{)}.$
(19)

Under the sup operator, $y^{\prime}$ is over all vectors such that
$\sum_{g}y^{\prime}_{g}=1$ and $y^{\prime}_{g}\geq 0,\forall g$, and
$V_{1},V_{2}\in{\mathbb{R}}$. Notice that we do not require (14) and (15) to
hold. Also, we could allow $\mu,\lambda_{1}$ and $\lambda_{2}$ to be in
${\mathbb{R}}$. We chose the signs to be $+$, $-$, and $-$ before them, and
restrict them in ${\mathbb{R}}_{\geq 0}$; this only increases the quantity.

For any for fixed $\mu,\lambda_{1},\lambda_{2}\in{\mathbb{R}}_{\geq 0}$ and
$y^{\prime}$, the objective (19) is maximized when $V_{1}=\lambda_{1}$ and
$V_{2}=\lambda_{2}$. Also, for fixed $\mu,\lambda_{1},\lambda_{2},V_{1}$ and
$V_{2}$, the objective is linear in $y^{\prime}$. So it is maximized when
$y^{\prime}$ is a vertex point of the simplex. That is $y^{\prime}_{g}=1$ for
some size-configuration $g$, and $y^{\prime}_{g^{\prime}}=0$ for every
$g^{\prime}\neq g$. Therefore, (19) is equal to

$\displaystyle\inf_{\mu,\lambda_{1},\lambda_{2}\in{\mathbb{R}}_{\geq
0}}\quad\sup_{g}\quad$
$\displaystyle\big{(}1-\frac{\alpha}{2}\big{)}\sum_{a\in
g}a^{2}-\frac{\alpha}{2}\big{(}\sum g\big{)}^{2}+\mu\big{(}\sum
g\big{)}-\lambda_{1}v_{1}(g)-\lambda_{2}v_{2}(g)$
$\displaystyle+\frac{1}{2}L^{2}-\mu
L-\frac{1}{2}+\frac{1}{2}(\lambda_{1}^{2}+\lambda_{2}^{2}).$ (20)

To handle the issues raised by the open intervals, we redefine $v_{1}(g)$ and
$v_{2}(g)$ in a slightly different way (the definition of $v_{0}(g)$ is
irrelevant in this case). First, we assume in the definition of size-
configurations, each $a\in g$ is associated with one of the 4 types: type-s,
type-1, type-2 and type-3. The following conditions must be satisfied:

  * •

If $a$ is of type-s, then $a\in(0,2]$;

  * •

If $a$ is of type-1, then $a\in[2,4]$;

  * •

If $a$ is of type-2, then $a\in[4,8]$;

  * •

If $a$ is of type-b, then $a\geq 8$.

Then we redefine $v_{1}(g)$ and $v_{2}(g)$ as the total value of type-1 and
type-2 elements in $g$ respectively. Now, the element $2\in g$ can contribute
to either $v_{1}(g)$ or $v_{2}(g)$. This slight modification will not change
the value of (20).

By Lemma 4.3, we can restrict $g$ to satisfy the following property: the sum
of the numbers in $g$, excluding the smallest one, is less than $L$. We say a
number $a>0$ is flexible if $a\notin\\{2,4,8\\}$. We then prove

######  Lemma 4.5.

In (20), we can restrict ourselves to the multi-sets $g$ containing at most 1
flexible element.

###### Proof.

Notice that if $g$ contains one element that is at least $4>L$, then it is the
only element in $g$. Assume there are two flexible elements
$b,b^{\prime}\in(0,4)$ in $g$. There are 4 numbers $l,r,l^{\prime},r^{\prime}$
such that the following conditions hold.

  * •

$l<b<r$ and $l^{\prime}<b^{\prime}<r^{\prime}$.

  * •

The three numbers $l,b$ and $r$ are all in $[0,2]$, or all in $[2,4]$. This
also holds for $l^{\prime},b^{\prime}$ and $r^{\prime}$.

  * •

At least one of $l$ and $r^{\prime}$ is in $\\{0,2,4\\}$. This also holds for
$r$ and $l^{\prime}$.

  * •

$l+r^{\prime}=b+b^{\prime}=r+l^{\prime}$.

Therefore, $(b,b^{\prime})$ is a convex combination of $(l,r^{\prime})$ and
$(r,l^{\prime})$. Say
$(b,b^{\prime})=\beta(l,r^{\prime})+(1-\beta)(r,l^{\prime})$ for some
$\beta\in[0,1]$. By changing $\\{b,b^{\prime}\\}$ to $\\{l,r^{\prime}\\}$ and
$\\{r,l^{\prime}\\}$ respectively, we obtain two multi-sets $g^{\prime}$ and
$g^{\prime\prime}$. Moreover, we can make the type of $l$ and $r$ the same as
that of $b$, and the type of $l^{\prime}$ and $r^{\prime}$ the same as that of
$b^{\prime}$. $g^{\prime}$ and $g^{\prime\prime}$ may contain $0$, but this is
not an issue as removing $0$ from the set does not change the objective.

Then we have $\sum_{a\in g}a^{2}<\beta\sum_{a\in
g^{\prime}}a^{2}+\beta\sum_{a\in g^{\prime\prime}}a^{2}$, $(\sum g)=(\sum
g^{\prime})=(\sum g^{\prime\prime})$, $v_{1}(g)=\beta
v_{1}(g^{\prime})+(1-\beta)v_{1}(g^{\prime\prime})$ and $v_{2}(g)=\beta
v_{2}(g^{\prime})+(1-\beta)v_{2}(g^{\prime\prime})$. As
$1-\frac{\alpha}{2}\geq 0$, one of $g$ and $g^{\prime}$ has a larger objective
than $g$ in (20), for any $\mu,\lambda_{1},\lambda_{2}\in{\mathbb{R}}_{\geq
0}$. Therefore, we can disregard $g$. ∎

Figure 3: The 6 cases for Lemma 4.6. Each row of line segments represents a
case in Lemma 4.6. Each line segment between two dots represent an element
whose value is the length of the line segment. Each ray represents a flexible
element (whose length is not determined) and the cross represents the
rightmost endpoint it can reach. Dashed line segments represent type-s or
type-b elements, black solid line segments represent type-1 elements, and red
solid line segments represent type-2 elements.

######  Lemma 4.6.

To compute in (20), it suffices to consider the one of the following 6 cases
for $g$ (See Figure 3):

  1. 1)

$g=\\{a_{1}\\}$. $a_{1}$ is in $(0,2]$ of type-s, in $[2,4]$ of type-1, in
$[4,8]$ of type-2, or in $[8,\infty)$ of type-b. There are 4 cases here.

  2. 2)

$g=\\{a_{1},a_{2}\\}$. $a_{1}$ is $2$ of type-s. $a_{2}$ is in $[0,2]$ of
type-$s$, or in $[2,4]$ of type-$1$. There are 2 cases here.

###### Proof.

Recall the two properties we can impose on $g$. The sum of elements in $g$,
excluding the smallest element, is less than $L<4$. $g$ contains at most one
element outside $\\{2,4,8\\}$. Moreover, if $a=2\in g$, we can assume $a$ is
of type-s; if $a=8\in g$, we can assume $a$ is of type-b. This can only
increase the objective. Simple enumeration gives the 6 cases. ∎

#### Analysis of Sub-Program (18)

Finally, we consider sub-program (18). Similar to the argument for sub-program
(17), an element $a\in g$ is one of the following 5 types: type-s, type-0,
type-1,type-2 and type-b. Moreover,

  * •

If $a$ is of type-s, then $a\in(0,1]$;

  * •

If $a$ is of type-0, then $a\in[1,2]$;

  * •

If $a$ is of type-1, then $a\in[2,4]$;

  * •

If $a$ is of type-2, then $a\in[4,8]$;

  * •

If $a$ is of type-b, then $a\geq 8$.

Redefine $v_{0}(g),v_{1}(g)$ and $v_{2}(g)$ to be the sum of elements in $g$
of type-$0$, type-$1$ and type-$2$ respectively. Following a similar argument
as before, the value of the program is at most

$\displaystyle\inf_{\mu,\lambda_{0},\lambda_{1},\lambda_{2}\in{\mathbb{R}}_{\geq
0}}\quad\sup_{g}\quad$
$\displaystyle\big{(}1-\frac{\alpha}{2}\big{)}\sum_{a\in
g}a^{2}-\frac{\alpha}{2}\big{(}\sum g\big{)}^{2}+\mu\big{(}\sum
g\big{)}-\lambda_{0}v_{0}(g)-\lambda_{1}v_{1}(g)-\lambda_{2}v_{2}(g)$
$\displaystyle+\frac{1}{2}L^{2}-\mu
L+\frac{1}{2}(\lambda_{0}^{2}+\lambda_{1}^{2}+\lambda_{2}^{2}).$ (21)

Similarly, we say $a$ is flexible if $a\notin\\{1,2,4,8\\}$. We can again
prove the following lemma:

######  Lemma 4.7.

In (21), we can restrict ourselves to the multi-sets $g$ containing at most 1
flexible element.

Figure 4: The 23 cases in Lemma 4.8. The legends are the same as those in
Figure 3, except now we have type-0 elements, denoted by thin solid line
segments.

######  Lemma 4.8.

To compute in (21), it suffices to consider the one of the following 23 cases
for $g$:

  1. 1)

$g=\\{a_{1}\\}$. $a_{1}$ is in $(0,1]$ of type-s, in $[1,2]$ of type-0, in
$[2,4]$ of type-1, in $[4,8]$ of type-2, or in $[8,\infty)$ of type-b. There
are 5 cases here.

  2. 2)

$g=\\{a_{1},a_{2}\\}$. $a_{1}$ is 1 of type-s, 2 of type-0, or 2 of type-1.
$a_{2}$ is in $(0,1]$ of type-s, in $[1,2]$ of type-0, or in $[2,4]$ of
type-1. There are 9 cases here.

  3. 3)

$g=\\{a_{1},a_{2},a_{3}\\}$. $a_{1}=1$ is of type-s. $a_{2}$ is $1$ of type-s,
$2$ of type-0, or $2$ of type-1. $a_{3}$ is in $(0,1]$ of type-s, or $[1,2]$
of type-0. There are 6 cases here.

  4. 4)

$g=\\{a_{1},a_{2},a_{3}\\}$. $a_{1}=a_{2}=1$ of type-s, $a_{3}\in[2,4]$ of
type-1.

  5. 5)

$g=\\{a_{1},a_{2},a_{3},a_{4}\\}$. $a_{1}=a_{2}=a_{3}=1$ is of type-s, $a_{2}$
is in $(0,1]$ of type-s, or in $[1,2]$ of type-0. There are 2 cases here.

###### Proof.

Again, we can require $g$ to satisfy the following two properties. The sum of
elements in $g$ excluding the smallest one is less than $L<4$. There are at
most 1 element in $g$ outside $\\{1,2,4,8\\}$. If $a=1\in g$, then $a$ is of
type-s. Exhaustive enumeration gives the 23 cases. ∎

#### Parameters for sub-programs (17) and (18)

We break our interval $[2,4)$ for $L$ into 10 sub-intervals, the $i$-th
interval being $[2^{1+(o-1)/10},2^{1+o/10})$. For each interval of $L$, we
give the parameters $\mu,\lambda_{1},\lambda_{2}\in{\mathbb{R}}_{\geq 0}$ for
(20) and $\mu,\lambda_{0},\lambda_{1},\lambda_{2}\in{\mathbb{R}}_{\geq 0}$ for
(21), and the overall $\alpha_{L}$ in Table 1. Notice that $L$ has an equal
probability of falling into the 10 intervals.
$\operatorname*{\mathbb{E}}_{\beta}[\alpha_{L}]$ is the average of the
$\alpha_{L}$ values over the 10 intervals, which is less than $1.358<1.36$.

$L$ | $\frac{3}{2}-\frac{2}{L^{2}}$ | Parameters for (20) | Parameters for (21) | $\alpha_{L}$
---|---|---|---|---
$\mu$ | $\lambda_{1}$ | $\lambda_{2}$ | $\mu$ | $\lambda_{0}$ | $\lambda_{1}$ | $\lambda_{2}$
$[2^{1},2^{1.1})$ | 1.0648 | 2.060000 | 0.08 | 0.00 | 2.072000 | 0.3145 | 0.3364 | 0.0828 | 1.376228
$[2^{1.1},2^{1.2})$ | 1.1211 | 2.293595 | 0.16 | 0.04 | 2.220500 | 0.3154 | 0.3642 | 0.1604 | 1.370445
$[2^{1.2},2^{1.3})$ | 1.1702 | 2.458214 | 0.22 | 0.16 | 2.508757 | 0.3178 | 0.4442 | 0.3200 | 1.364426
$[2^{1.3},2^{1.4})$ | 1.2129 | 2.634649 | 0.32 | 0.28 | 2.720583 | 0.3220 | 0.5288 | 0.4532 | 1.356049
$[2^{1.4},2^{1.5})$ | 1.2500 | 2.823747 | 0.42 | 0.40 | 2.874152 | 0.3255 | 0.5942 | 0.5472 | 1.349022
$[2^{1.5},2^{1.6})$ | 1.2824 | 2.998133 | 0.48 | 0.48 | 2.961363 | 0.3279 | 0.6310 | 0.5984 | 1.344238
$[2^{1.6},2^{1.7})$ | 1.3106 | 3.213319 | 0.56 | 0.56 | 3.150265 | 0.3292 | 0.6886 | 0.6752 | 1.341530
$[2^{1.7},2^{1.8})$ | 1.3351 | 3.346480 | 0.60 | 0.60 | 3.343231 | 0.3296 | 0.7362 | 0.7336 | 1.340912
$[2^{1.8},2^{1.9})$ | 1.356413 | 3.412558 | 0.60 | 0.60 | 3.404549 | 0.3273 | 0.7398 | 0.7380 | 1.356413
$[2^{1.9},2^{2})$ | 1.3750 | 3.470883 | 0.60 | 0.60 | 3.507084 | 0.3009 | 0.7328 | 0.7324 | 1.375000
Table 1: The parameters for the three sub-programs (16), (17) and (18), for
each interval of $L$. The first column contains the intervals for $L$. The
second column gives the $\frac{3}{2}-\frac{2}{L^{2}}$ for the right end point
$L$ of each interval, which is the minimum $\alpha_{L}$ needed for sub-program
(16). The next 3 columns give the parameters $\mu,\lambda_{1},\lambda_{2}$ for
(20). The next 4 columns give the parameters
$\mu,\lambda_{1},\lambda_{2},\lambda_{3}$ for (21). The final column gives the
$\alpha_{L}$ value for each interval of $L$. The average of the 10 values of
$\alpha_{L}$ is less than $1.36$.

We then describe how to check if the parameters are valid using a computer
program. Focus on each interval $[2^{1+(o-1)/10},2^{1+o/10})$ for $L$. For
sub-program (16), we can simply check if
$\alpha_{L}\geq\frac{3}{2}-\frac{2}{L^{2}}$ for $L=2^{1+o/10}$; the values of
$\frac{3}{2}-\frac{2}{L^{2}}$ for $L=2^{1+o/10}$ are given in the table. For
sub-program (17), we consider (20), for the given
$\mu,\lambda_{1},\lambda_{2},\alpha=\alpha_{L}$ and each case of $g$ in Lemma
4.6. For a fixed $g$ in the case, the objective is a quadratic function of $L$
with the quadratic term being $\frac{L^{2}}{2}$. Therefore, the worst $L$ is
one of the two end points $2^{1+(o-1)/10}$ and $2^{1+o/10}$ of the interval.
So, we only need to check the two values for $L$. Fixing $L$ and letting $a$
be only flexible element in $g$, the quantity in (20) is a quadratic function
$a$. Therefore, we can easily find the maximum of the objective over all valid
$a$’s for the case. Similarly, we can check the validity of the parameters for
(18) using (21). Using our checker program with the given parameters, we can
certify that the $\alpha_{L}$ values are feasible for (9). The source code for
the checker can be found at

  * •

https://github.com/temporary6724722/WeightedCompletionTime.git.

We also describe briefly how we search for the parameters
$\mu,\lambda_{1},\lambda_{2}$ for (20) and
$\mu,\lambda_{0},\lambda_{1},\lambda_{2}$ for (21), though this is not needed
to for the proof of our approximation ratio. We only describe our parameter
searching algorithm for (20); the procedure for (21) uses similar ideas. We
enumerate $\mu,\lambda_{1}$ and $\lambda_{2}$, each parameter having a lower
bound, an upper bound and a step size. That means, we search for the optimum
vector $(\mu,\lambda_{1},\lambda_{2})$ within a box using some step-sizes. For
a fixed $\mu,\lambda_{1}$ and $\lambda_{2}$, the best $\alpha_{L}$ can be
determined using binary search up to any precision. Then, once we find the
optimum $(\mu,\lambda_{1},\lambda_{2})$, we run a fine-grained searching
procedure in a smaller box around the $(\mu,\lambda_{1},\lambda_{2})$ we
found, with smaller step sizes for the three parameters. Once we find the
optimum $(\mu^{\prime},\lambda^{\prime}_{1},\lambda^{\prime}_{2})$, we run a
third round of even more fine-grained search procedure around it, which will
give our final parameters for $\mu,\lambda_{1}$ and $\lambda_{2}$. We also
tried different values of $\rho$, but it seems that the gain is small. Thus we
decided to use the simple choice of $\rho=2$.

##  5 Discussions

In this paper, we developed a $1.36$-approximation algorithm for the unrelated
machine weighted completion time scheduling problem, using an iterative
rounding procedure. Unlike previous algorithms, which impose the non-positive
correlation requirement between any two edges $ij$ and $ij^{\prime}$, we only
require non-positive correlation to hold between an unmarked edge
$e\in\delta^{k,\mathrm{umk}}_{i}$ and the set $\delta^{k,\mathrm{mk}}_{i}$ of
marked edges as a whole. With this relaxation, our algorithm chooses at most
one edge from each group $\delta^{k,\mathrm{mk}}_{i}$, leading to the upper
bound in (6).

An immediate open problem is to provide a tight upper bound on the ratio
between the bounds in (6) and (5), for a fixed $i$ and $j^{*}$. Our analysis
falls short of achieving this goal for two reasons. Firstly, we only consider
three job classes $J_{k}$, as we have to guess whether $V_{k}\geq 2^{k}$ or
not for every $k$ in program (11). Increasing the number of job classes would
require us to consider more sub-programs. Secondly, we did not exploit the
property that the $z$-vector is the same for every random value
$\beta\in[1,\rho=2)$. In our analysis, we define the parameter $L\in[2,4)$,
and compute the worst ratio for every $L$. However, the worst case scenarios
for different $L$ values may be inconsistent. Exploring the connections
between different $L$ values would lead to a tighter analysis. Additionally,
it would be interesting to give a clean analytical proof of the ratio, without
significantly degrading the approximation performance.

## References

  * [1] Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, Ionnis Milis, Maurice Queyranne, Martin Skutella, Cliff Stein, and Maxim Sviridenko.  Approximation schemes for minimizing average weighted completion time with release dates.  In FOCS, 1999.
  * [2] Nikhil Bansal, Aravind Srinivasan, and Ola Svensson.  Lift-and-round to improve weighted completion time on unrelated machines.  In STOC 2016, pages 156–167, 2016.
  * [3] James Bruno, Edward G Coffman Jr, and Ravi Sethi.  Scheduling independent tasks to reduce mean finishing time.  Communications of the ACM, 17(7):382–387, 1974.
  * [4] Chandra Chekuri and Sanjeev Khanna.  A ptas for minimizing weighted completion time on uniformly related machines.  In ICALP 2001, pages 848–861. Springer, 2001.
  * [5] Chandra Chekuri and Sanjeev Khanna.  Approximation algorithms for minimizing average weighted completion time.  2004\.
  * [6] M. Fahrbach, Z. Huang, R. Tao, and M. Zadimoghaddam.  Edge-weighted online bipartite matching.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 412–423, Los Alamitos, CA, USA, nov 2020. IEEE Computer Society.
  * [7] Uriel Feige.  On allocations that maximize fairness.  In SODA, 2008.
  * [8] Michael R Garey and David S Johnson.  Computers and intractability, volume 29.  wh freeman New York, 2002.
  * [9] David G. Harris.  Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time.  In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2275–2304.
  * [10] 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.
  * [11] WA Horn.  Minimizing average flow time with parallel machines.  Operations Research, 21(3):846–847, 1973.
  * [12] Sungjin Im and Shi Li.  Improved approximations for unrelated machine scheduling.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2917–2946.
  * [13] Sungjin Im and Maryam Shadloo.  Weighted completion time minimization for unrelated machines via iterative fair contention resolution [extended abstract].  In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, page 2790–2809, 2020.
  * [14] Christos Kalaitzis, Ola Svensson, and Jakub Tarnawski.  Unrelated machine scheduling of jobs with uniform smith ratios.  In SODA, 2017.
  * [15] VS Anil Kumar, Madhav V Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan.  Minimum weighted completion time.  In Encyclopedia of Algorithms, pages 544–546. Springer, 2008.
  * [16] Jan Karel Lenstra, David B Shmoys, and Éva Tardos.  Approximation algorithms for scheduling unrelated parallel machines.  Mathematical programming, 46(1-3):259–271, 1990.
  * [17] Shi Li.  Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations.  SIAM Journal on Computing, 49(4):FOCS17–409–FOCS17–440, 2020\.
  * [18] Andreas S Schulz and Martin Skutella.  Scheduling unrelated machines by randomized rounding.  SIAM Journal on Discrete Mathematics, 15(4):450–469, 2002.
  * [19] Petra Schuurman and Gerhard J Woeginger.  Polynomial time approximation algorithms for machine scheduling: Ten open problems.  Journal of Scheduling, 2(5):203–213, 1999.
  * [20] Jay Sethuraman and Mark S Squillante.  Optimal scheduling of multiclass parallel machines.  In SODA, pages 963–964, 1999.
  * [21] Martin Skutella.  Convex quadratic and semidefinite programming relaxations in scheduling.  J. ACM, 48(2):206–242, 2001.
  * [22] Martin Skutella and Gerhard J Woeginger.  A ptas for minimizing the total weighted completion time on identical parallel machines.  Mathematics of Operations Research, 25(1):63–75, 2000.
  * [23] Maxim Sviridenko and Andreas Wiese.  Approximating the configuration-LP for minimizing weighted sum of completion times on unrelated machines.  In IPCO. 2013.