Approximation Algorithms: Unrelated Machine Scheduling and Generalized Assignment

This is the lecture notes from Chandra Chekuri's CS583 course on Approximation Algorithms. Chapter 6: Unrelated Machine Scheduling and Generalized Assignment. You can read Chapter 7: Congestion Minimization in Networks, here. Chapter 5: Load Balancing and Bin Packing, here.

Chapter 6

This chapter is based on notes first scribed by Alina Ene.

6.1 Scheduling on Unrelated Parallel Machines

We have a set

J

n

jobs, and a set

M

m

machines. The processing time of job

i

p_{i j}

on machine

j

. Let

f : J \to M

be a function that assigns each job to exactly one machine. The makespan of

f

max_{1 \leq j \leq m} \sum_{i : f (i) = j} p_{i j}

, where

\sum_{i : f (i) = j} p_{i j}

is the total processing time of the jobs that are assigned to machine

j

. In the Scheduling on Unrelated Parallel Machines problem, the goal is to find an assignment of jobs to machines of minimum makespan.

We can write an LP for the problem that is very similar to the routing LP from the previous lecture. For each job

i

and each machine

j

, we have a variable

x_{i j}

that denotes whether job

i

is assigned to machine

j

. We also have a variable

λ

for the makespan. We have a constraint for each job that ensures that the job is assigned to some machine, and we have a constraint for each machine that ensures that the total processing time of jobs assigned to the machines is at most the makespan

λ

\begin{aligned} minimize & λ \\ subject to & \sum_{j \in M} x_{i j} = 1 & \forall i \in J \\ \sum_{i \in J} x_{i j} p_{i j} \leq λ & \forall j \in M \\ x_{i j} \geq 0 & \forall i \in J, j \in M \end{aligned}

The above LP is very natural, but unfortunately it has unbounded integrality gap. Suppose that we have a single job that has processing time

T

on each of the machines. Clearly, the optimal schedule has makespan

T

. However, the LP can schedule the job to the extend of

1 / m

on each of the machines, i.e., it can set

x_{1 j} = 1 / m

for all

j

, and the makespan of the resulting fractional schedule is only

T / m

To overcome this difficulty, we modify the LP slightly. Suppose we knew that the makespan of the optimal solution is equal to

λ

, where

λ

is some fixed number. If the processing time

p_{i j}

of job

i

on machine

j

is greater than

λ

, job

i

is not scheduled on machine

j

, and we can strengthen the LP by setting

x_{i j}

to 0 or equivalently, by removing the variable. More precisely, let

S_{λ} = {(i, j) ∣ i \in J, j \in M, p_{i j} \leq λ}

. Given a value

λ

, we can write the following LP for the problem.

\begin{aligned} \underline{L P (λ)} \\ \sum_{j : (i, j) \in S_{λ}} x_{i j} = 1 & \forall i \in J \\ \sum_{i : (i, j) \in S_{λ}} x_{i j} p_{i j} \leq λ & \forall j \in M \\ x_{i j} \geq 0 & \forall (i, j) \in S_{λ} \end{aligned}

Note that the LP above does not have an objective function. In the following, we are only interested in whether the LP is feasible, i.e, whether there is an assignment that satisfies all the constraints. Also, we can think of

λ

as a parameter and

L P (λ)

as a family of LPs, one for each value of the parameter. A useful observation is that, if

λ

is a lower bound on the makespan of the optimal schedule,

L P (λ)

is feasible and it is a valid relaxation for the Scheduling on Unrelated Parallel Machines problem.

Lemma 6.1. Let $λ^{*}$ be the minimum value of the parameter $λ$ such that $L P (λ)$ is feasible. We can find $λ^{*}$ in polynomial time.

Proof. For any fixed value of

λ

, we can check whether

L P (λ)

is feasible using a polynomial-time algorithm for solving LPs. Thus we can find

λ^{*}

using binary search starting with the interval

[0, \sum_{i, j} p_{i j}]

In the following, we will show how to round a solution to

L P (λ^{*})

in order to get a schedule with makespan at most

2 λ^{*}

. As we will see shortly, it will help to round a solution to

L P (λ^{*})

that is a vertex solution.

Let

x

be a vertex solution to

L P (λ^{*})

. Let

G

be a bipartite graph on the vertex set

J \cup M

that has an edge

i j

for each variable

x_{i j} \neq 0

. We say that job

i

is fractionally set if

x_{i j} \in (0, 1)

for some

j

. Let

F

be the set of all jobs that are fractionally set, and let

H

be a bipartite graph on the vertex set

F \cup M

that has an edge

i j

for each variable

x_{i j} \in (0, 1)

; note that

H

is the induced subgraph of

G

F \cup M

. As shown in Lemma 6.2, the graph

H

has a matching that matches every job in

F

to a machine, and we will it in the rounding algorithm.

Lemma 6.2. The graph $G$ has a matching that matches every job in $F$ to a machine.

We are now ready to give the rounding algorithm.

SUPM-Rounding

Find

λ^{*}

Find a vertex solution

x

L P (λ^{*})

For each

i

and

j

such that

x_{i j} = 1

, assign job

i

to machine

j

Construct the graph

H

Find a maximum matching

M

H

Assign the fractionally set jobs according to the matching

M

Theorem 6.1. Consider the assignment constructed by SUPM-Rounding. Each job is assigned to a machine, and the makespan of the schedule is at most $2 λ^{*}$ .

Proof. By Lemma 6.2, the matching

M

matches every fractionally set job to a machine and therefore all of the jobs are assigned. After assigning all of the integrally set jobs, the makespan (of the partial schedule) is at most

λ^{*}

. Since

M

is a matching, each machine receives at most one additional job. Let

i

be a fractionally set job, and suppose that

i

is matched (in

M

) to machine

j

. Since the pair

(i, j)

is in

S_{λ^{*}}

, the processing time

p_{i j}

is at most

λ^{*}

, and therefore the total processing time of machine

j

increases by at most

λ

after assigning the fractionally set jobs. Therefore the makespan of the final schedule is at most

2 λ^{*}

Exercise 6.1. Give an example that shows that Theorem 6.1 is tight. That is, give an instance and a vertex solution such that the makespan of the schedule SUPM-Rounding is at least

(2 - o (1)) λ^{*}

Since

λ^{*}

is a lower bound on the makespan of the optimal schedule, we get the following corollary.

Corollary 6.2. SUPM-Rounding achieves a $2$ -approximation.

Now we turn our attention to Lemma 6.2 and some other properties of vertex solutions to

L P (λ)

. The following can be derived from the rank lemma which is described in Chapter A. Here we give a self-contained proof.

Lemma 6.3. If $L P (λ)$ is feasible, any vertex solution has at most $m + n$ non-zero variables and it sets at least $n - m$ of the jobs integrally.

Proof. Let

x

be a vertex solution to

L P (λ)

. Let

r

denote the number of pairs in

S_{λ}

. Note that

L P (λ)

has

r

variables, one for each pair

(i, j) \in S_{λ}

. If

x

is a vertex solution, it satisfies

r

of the constraints of

L P (λ)

with equality. The first set of constraints consists of

n

constraints, and the second set of constraints consists of

m

constraints. Therefore at least

r - (m + n)

of the tight constraints are from the third set of constraints, i.e., at least

r - (m + n)

of the variables are set to zero.

We say that job

i

is set fractionally if

x_{i j} \in (0, 1)

for some

j

; job

i

is set integrally if

x_{i j} \in {0, 1}

for all

j

. Let

I

and

F

be the set of jobs that are set integrally and fractionally (respectively). Clearly,

| I | + | F | = n

. Any job

i

that is fractionally set is assigned (fractionally) to at least two machines, i.e., there exist

j \neq ℓ

such that

x_{i j} \in (0, 1)

and

x_{i ℓ} \in (0, 1)

. Therefore there are at least

2 | F |

distinct non-zero variables corresponding to jobs that are fractionally set. Additionally, for each job

i

that is integrally set, there is a variable

x_{i j}

that is non-zero. Thus the number of non-zero variables is at least

| I | + 2 | F |

. Hence

| I | + | F | = n

and

| I | + 2 | F | \leq m + n

, which give us that

| I |

is at least

n - m

Definition 6.3. A connected graph is a pseudo-tree if the number of edges is at most the number of vertices. A graph is a pseudo-forest if each of its connected components is a pseudo-tree.

Lemma 6.4. The graph $G$ is a pseudo-forest.

Proof. Let

C

be a connected component of

G

. We restrict

L P (λ)

and

x

to the jobs and machines in

C

to get

{L P}^{'} (λ)

and

x^{'}

. Note that

x^{'}

is a feasible solution to

{L P}^{'} (λ)

. Additionally,

x^{'}

is a vertex solution to

{L P}^{'} (λ)

. If not,

x^{'}

is a convex combination of two feasible solutions

x_{1}^{'}

and

x_{2}^{'}

{L P}^{'} (λ)

. We can extend

x_{1}^{'}

and

x_{2}^{'}

to two solutions

x_{1}

and

x_{2}

L P (λ)

using the entries of

x

that are not in

x^{'}

. By construction,

x_{1}

and

x_{2}

are feasible solutions to

L P (λ)

. Additionally,

x

is a convex combination of

x_{1}

and

x_{2}

, which contradicts the fact that

x

is a vertex solution. Thus

x^{'}

is a vertex solution to

{L P}^{'} (λ)

and, by Lemma 6.3,

x^{'}

has at most

n^{'} + m^{'}

non-zero variables, where

n^{'}

and

m^{'}

are the number of jobs and machines in

C

. Thus

C

has

n^{'} + m^{'}

vertices and at most

n^{'} + m^{'}

edges, and therefore it is a pseudo-tree.

Proof. of Lemma 6.2 Note that each job that is integrally set has degree one in

G

. We remove each integrally set job from

G

; note that the resulting graph is

H

. Since we removed an equal number of vertices and edges from

G

, it follows that

H

is a pseudo-forest as well. Now we construct a matching

M

as follows.

Note that every job vertex has degree at least 2, since the job is fractionally assigned to at least two machines. Thus all of the leaves (degree-one vertices) of

H

are machines. While

H

has at least one leaf, we add the edge incident to the leaf to the matching and we remove both of its endpoints from the graph. If

H

does not have any leaves,

H

is a collection of vertex-disjoint cycles, since it is a pseudo-forest. Moreover, each cycle has even length, since

H

is bipartite. We construct a perfect matching for each cycle (by taking alternate edges), and we add it to our matching.

Exercise 6.2. (Exercise

17.1

in ^[1]) Give a proof of Lemma 6.2 using Hall's theorem.

6.2 Generalized Assignment Problem

The Generalized Assignment problem is a generalization of the Scheduling on Unrelated Parallel Machines problem in which there are costs associated with each job-machine pair, in addition to a processing time. More precisely, we have a set

J

n

jobs, a set

M

m

machines, and a target

λ

. The processing time of job

i

p_{i j}

on machine

j

, and the cost of assigning job

i

to machine

j

c_{i j}

. Let

f : J \to M

be a function that assigns each job to exactly one machine. The assignment

f

is feasible if its makespan is at most

λ

(recall that

λ

is part of the input), and its cost is

\sum_{i} c_{i f (i)}

. In the Generalized Assignment problem, the goal is to construct a minimum cost assignment

f

that is feasible, provided that there is a feasible assignment.

Remark 6.1. We could allow each machine

M_{j}

to have a different capacity

c_{j}

which is more natural in certain settings. However, since

p_{i j}

values are allowed to depend on

j

we can scale them to ensure that

c_{j} = λ

for every

j

without loss of generality.

In the following, we will show that, if there is an assignment of cost

C

and makespan at most

λ

, then we can construct a schedule of cost at most

C

and makespan at most

2 λ

. In fact the assignment will have a stronger property that the load on a a machine exceeds

λ

due to at most one job.

As before, we let

S_{λ}

denote the set of all pairs

(i, j)

such that

p_{i j} \leq λ

. We can generalize the relaxation

L P (λ)

from the previous section to the following LP.

\begin{aligned} \underline{GAP-LP} \\ min & \sum_{\begin{array}{c} (i, j) \in S_{λ} \end{array}} x_{i j} c_{i j} \\ subject to & \sum_{j : (i, j) \in S_{λ}} x_{i j} = 1 & \forall i \in J \\ \sum_{i : (i, j) \in S_{λ}} x_{i j} p_{i j} \leq λ & \forall j \in M \\ x_{i j} \geq 0 & \forall (i, j) \in S_{λ} \end{aligned}

Since we also need to preserve the costs, we can no longer use the previous rounding; in fact, it is easy to see that the previous rounding is arbitrarily bad for the Generalized Assignment problem. However, we will still look for a matching, but in a slightly different graph.

But before we give the rounding algorithm for the Generalized Assignment problem, we take a small detour into the problem of finding a minimum-cost matching in a bipartite graph. In the Minimum Cost Biparite Matching problem, we are given a bipartite graph

B = (V_{1} \cup V_{2}, E)

with costs

c_{e}

on the edges, and we want to construct a minimum cost matching

M

that matches every vertex in

V_{1}

, if there is such a matching. For each vertex

v

, let

δ (v)

be the set of all edges incident to

v

. We can write the following LP for the problem.

\begin{aligned} \underline{BipartiteMatching (B)} \\ min & \sum_{e \in E (B)} c_{e} y_{e} \\ subject to & \sum_{e \in δ (v)} y_{e} = 1 & \forall v \in V_{1} \\ \sum_{e \in δ (v)} y_{e} \leq 1 & \forall v \in V_{2} \\ y_{e} \geq 0 & \forall e \in E (B) \end{aligned}

The following is well-known in combinatorial optimization ^[2].

Theorem 6.4. For any bipartite graph $B$ , any vertex solution to BipartiteMatching $(B)$ is an integer solution. Moreover, given a feasible fractional solution $y$ , we can find in polynomial time a feasible solution $z$ such that $z$ is integral and

\sum_{e \in E (B)} c_{e} z_{e} \leq \sum_{e \in E (B)} c_{e} y_{e} .

In the rest of the section we give two different proofs that establish our claimed result. One is based on the first work that gave this result ^[3], and the other is based on iterative rounding ^[4].

6.2.1 Shmoys-Tardos Rounding

Let

x

be an optimal vertex solution to GAP-LP. As before, we want to construct a graph

G

that has a matching

M

that matches all jobs. The graph

G

will now have costs on its edges and we want a matching of cost at most

C

. Recall that for Scheduling on Unrelated Parallel Machines we defined a bipartite graph on the vertex set

J \cup M

that has an edge

i j

for every variable

x_{i j}

that is non-zero. We can construct the same graph for Generalized Assignment, and we can assign a cost

c_{i j}

to each edge

i j

. If the solution

x

was actually a fractional matching - that is, if

x

was a feasible solution to BipartiteMatching

(G)

- Theorem 6.4 would give us the desired matching. The solution

x

satisfies the constraints corresponding to vertices

v \in J

, but it does not necessarily satisfy the constraints corresponding vertices

v \in M

, since a machine can be assigned more than one job. To get around this difficulty, we will introduce several nodes representing the same machine, and we will use

x

to construct a fractional matching for the resulting graph.

The fractional solution

x

assigns

\sum_{i \in J} x_{i j}

jobs to machine

j

; let

k_{j} = ⌈ \sum_{i \in J} x_{i j} ⌉

. We construct a bipartite graph

G

as follows. For each job

i

, we have a node

i

. For each machine

j

, we have

k_{j}

nodes

(j, 1), \dots, (j, k_{j})

. We can think of the nodes

(j, 1), \dots, (j, k_{j})

as slots on machine

j

. Since now we have multiple slots on each of the machines, we need a fractional assignment

y

that assigns a job to slots on the machines. More precisely,

y

has an entry

y_{i, (j, s)}

for each job

i

and each slot

(j, s)

that represents the fraction of job

i

that is assigned to the slot. We give the algorithm that constructs

y

from

x

below. Once we have the solution

y

, we add an edge between any job

i

and any machine slot

(j, s)

such that

y_{i, (j, s)}

is non-zero. Additionally, we assign a cost

c_{i, (j, s)}

to each edge

(i, (j, s))

G

that is equal to

c_{i j}

\underline{GreedyPacking (x)}

y = 0

«initialize $y$ to

0

s = 1

s

is the current bin»

R = 1

R

is the space available on bin

s

for

i = 1

h

«pack $x_{i j}$ into the bins»

x_{i j} \leq R

y_{i, (j, s)} = x_{i j}

R = R - x_{i j}

R = 0

s = s + 1

R = 1

else

y_{i, (j, s)} = R

y_{i, (j, s + 1)} = x_{i j} - R

«pack $x_{i j} - R$ in the next bin»

R = 1 - y_{i, (j, s + 1)}

s = s + 1

return

y

Figure 6.1: Constructing y from x.

When we construct

y

, we consider each machine in turn. Let

j

be the current machine. Recall that we want to ensure that

y

assigns at most one job to each slot; as such, we will think of each slot on machine

j

as a bin with capacity 1 . We "pack" jobs into the bins greedily. We only consider jobs

i

such that

p_{i j}

is at most

λ

; let

h

denote the number of such jobs. We assume without loss of generality that these are labeled as

1, 2, \dots, h

, and

p_{1 j} \geq p_{2 j} \geq \dots \geq p_{h j}

. Informally, when we construct

y

, we consider the jobs

1, 2, \dots, h

in this order. Additionally, we keep track of the bin that has not been filled and the amount of space

s

available on that bin. When we consider job

i

, we try to pack

x_{i j}

into the current bin: if there is at least

x_{i j}

space available, i.e.,

x_{i j} \leq s

, we pack the entire amount into the current bin; otherwise, we pack as much as we can into the current bin, and we pack the rest into the next bin. (See Figure 1 for an example.)

Lemma 6.5. The solution $y$ constructed by GreedyPacking is a feasible solution to BipartiteMatching $(G)$ . Moreover,

\sum_{(i, (j, s) \in E (G)} y_{i, (j, s)} c_{i, (j, s)} = \sum_{(i, j) \in S_{λ}} x_{i j} c_{i j} .

Proof. Note that, by construction,

x_{i j} = \sum_{s = 1}^{k_{j}} y_{i, (j, s)}

. Therefore, for any job

i

, we have

\sum_{(i, j, s)) \in δ (i)} y_{i, (j, s)} = \sum_{j : (i, j) \in S_{λ}} \sum_{s = 1}^{k_{j}} y_{i, (j, s)} = \sum_{j : (i, j) \in S_{λ}} x_{i j} = 1

Additionally, since we imposed a capacity of

1

on the bins associated with each slot, it follows that, for any slot

(j, s)

\sum_{(i, (j, s) \in δ ((j, s)))} y_{i, (j, s)} \leq 1

Therefore

y

is a feasible solution to BipartiteMatching

(G)

. Finally,

\sum_{(i, (j, s)) \in E (G)} y_{i, (j, s)} c_{i, (j, s)} = \sum_{i = 1}^{n} \sum_{j : (i, j) \in S_{λ}} \sum_{s = 1}^{k_{j}} y_{i, (j, s)} c_{i j} = \sum_{(i, j) \in S_{λ}} x_{i j} c_{i j}

Theorem 6.4 gives us the following corollary.

Corollary 6.5. The graph $G$ has a matching $M$ that matches every job and it has cost at most $\sum_{(i, j) \in S_{λ}} x_{i j} c_{i j}$ . Moreover, we can find such a matching in polynomial time.

\underline{GAP-Rounding}

let

x

be an optimal solution to GAP-LP

y = GreedyPacking (x)

construct the graph

G

construct a matching

M

G

such that

M

matches every job

and the cost of

M

is at most

\sum_{(i, j) \in S_{λ}} x_{i j} c_{i j}

for each edge

(i, (j, s)) \in M

assign job

i

to machine

j

Theorem 6.6. Let $C = \sum_{(i, j) \in S_{λ}} x_{i j} c_{i j}$ . The schedule returned by GAP-Rounding has cost at most $C$ and makespan at most $2 λ$ .

Proof. By Corollary 6.5, the cost of the schedule is at most

C

. Therefore we only need to upper bound the makespan of the schedule.

Consider a machine

j

. For any slot

(j, s)

on machine

j

, let

q_{j s} = max_{i : y_{i, j, j, s} > 0} p_{i j}

That is,

q_{j s}

is the maximum processing time of any pair

i j

such that job

i

is assigned (in

y

) to the slot

(j, s)

. It follows that the total processing time of the jobs that

M

assigns to machine

j

is at most

\sum_{s = 1}^{k_{j}} q_{j s}

Since GAP-LP has a variable

x_{i j}

only for pairs

(i, j)

such that

p_{i j}

is at most

λ

, it follows that

q_{j 1}

is at most

λ

. We restrict attention to the case when at least two slots are assigned to

j

, for otherwise it is easy to see that the load is atmost

λ

. Therefore we only need to show that

\sum_{s = 2}^{k_{j}} q_{j s}

is at most

λ

as well. Consider a slot

s

on machine

j

such that

s > 1

. Recall that we labeled the jobs that are relevant to machine

j

- that is, jobs

i

such that

p_{i j}

is at most

λ

- as

1, 2, \dots, h

such that

p_{1 j} \geq p_{2 j} \geq \dots \geq p_{h j}

. Consider a job

ℓ

that is assigned to slot

s

. Since GreedyPacking considers jobs in non-increasing order according to their processing times, the processing time

p_{ℓ j}

of job

ℓ

is at most the processing time of any job assigned to the slot

s - 1

. Therefore

p_{ℓ j}

is upper bounded by any convex combination of the processing times of the jobs that are assigned to the slot

s - 1

. Since the slot

s - 1

is full,

\sum_{i} y_{i, (j, s - 1)} = 1

and thus

p_{ℓ j}

is at most

\sum_{i} y_{i, (j, s - 1)} p_{i j}

. It follows that

\sum_{s = 2}^{k_{j}} q_{j s} \leq \sum_{s = 2}^{k_{j}} \sum_{i} y_{i, (j, s - 1)} p_{i j} \leq \sum_{s = 1}^{k_{j}} \sum_{i} y_{i, (j, s)} p_{i j}

By construction,

\sum_{s} y_{i, (j, s)} = x_{i j}

, and therefore

\sum_{s = 1}^{k_{j}} \sum_{i} y_{i, (j, s)} p_{i j} = \sum_{i} p_{i j} \sum_{s = 1}^{s} y_{i, (j, s)} = \sum_{i} p_{i j} x_{i j}

Since

x

is a feasible solution to the GAP-LP,

\sum_{s = 2}^{k_{j}} q_{j s} \leq \sum_{i} p_{i j} x_{i j} \leq λ

which completes the proof.

6.2.2 Iterative Rounding

Here we describe an alternative proof/algorithm that illustrates the iterative rounding framework that initially came out of Jain's seminal work ^[5]. Since then it has become a powerful technique in exact and approximation algorithms. We need some additional formalism to describe the algorithm. We will consider the input instance as being specified by a graph

G = (J \cup M, E)

where an edge

i j \in E

implies that

i

is allowed to be schedule on

j

and has size

p_{i j}

. It is also important to consider non-uniform capacities on the machines to allow for a recursive (or iterative) algorithm. Thus we will assume that each machine

M_{j}

has a capacity

b_{j}

. We will assume that

p_{i j} \leq b_{j}

for all

i j \in E

; in fact this assumption will not be needed until the very end when we analyze the approximation ratio. It is easy to generalize the LP relaxation for GAP-LP to handle non-uniform capacities and to handle the constraints specified by

G

. We will use the notation

δ (i)

and

δ (j)

to denote the edges incident to job

i

and machine

j

respectively.

\begin{aligned} \underline{GAP-LP} \\ min & \sum_{\begin{array}{c} (i, j) \in E \end{array}} c_{i j} x_{i j} \\ subject to & \sum_{j : (i, j) \in δ (i)} x_{i j} = 1 & \forall i \in J \\ \sum_{i : (i, j) \in E} p_{i j} x_{i j} \leq b_{j} & \forall j \in M \\ x_{i j} \geq 0 & \forall (i, j) \in E \end{aligned}

To explain the underlying intuition for iterated rounding approach in the specific context of GAP, consider the situation where each machine

j

has infinite capacity. In this case it is easy to find the minimum cost assignment. We simply assign each job

i

to the machine

j = \arg min_{j^{'} \in δ (i)} c_{i j^{'}}

which is the cheapest one that it is allowed to be assigned to. We also observe that if we drop all the capacity constraints from GAP-LP, and only leave the assignment constraints (

\sum_{j} x_{i j} = 1

for each

i

), then the optimum solution of this LP is the same as the one obtained by assigning each job to its cheapest allowed machine (one can also argue that the LP is an integer polytope). Now consider another scenario. Suppose each machine

j

has in-degree at most

k

G

- that is, there are only

k

jobs that can ever be assigned to any machine

j

. Now suppose we assign each job to its cheapest allowed machine. Clearly the cost is at most the optimum cost of any feasible solution. But what about the load? Since each machine had in-degree at most

k

we will load a machine

j

to at most

k b_{j}

. Thus, if

k = 2

we will only violate the machine's load by a factor of

2

. However, this seems to be very restrictive assumption. Now consider a less restrictive scenario where there is one machine

j

such that its in-degree is at most

2

. Then, in the LP relaxation, we can omit the constraint that limits its load since we are guaranteed that at most

2

jobs can be assigned to it (note that we still have the job assignment constraints which only allow a job to be assigned to machines according to the edges of

G

). Omitting constraints in an iterative fashion by taking advantage of sparsity in the basic feasible solution is the key idea.

To allow dropping of constraints we need some notation. Given an instance of GAP specified by

G = (J \cup M, E)

and

M^{'} \subseteq M

, we let

G A P L P (G, M^{'})

denote the LP relaxation for GAP where we only impose the load constraints for machines in

M^{'}

. In other words we drop the load constraints for

M ∖ M^{'}

. Note that jobs are still allowed to be assigned to machines in

M ∖ M^{'}

The key structural lemma that allows for iterated rounding is the following.

Lemma 6.6. Let $y$ be a basic feasible solution to $G A P L P (G, M^{'})$ . Then one of the following properties holds:

1. There is some $i j \in E$ such $y_{i j} = 0$ or $y_{i j} = 1$ .

2. There is a machine $j \in M^{'}$ such that $d (j) \leq 1$ .

3. There is a machine $j \in M^{'}$ such that deg $(j) = 2$ and $\sum_{i j} y_{i j} \geq 1$ .

Proof. Let

y

be a basic feasible solution. If

y_{i j} = 0

y_{i j} = 1

for some edge

i j \in E

we are done. Similarly if there is a machine

j \in M^{'}

with

d (j) \leq 1

we are done. Thus we restrict our attention to the case when

y_{i j}

is strictly fractional for every edge

i j \in E

and

d (j) > 1

for each machine

j \in M^{'}

. Note that

d e g (i) \geq 2

for each job

J

; otherwise

\deg (i) = 1

and in that case

y_{i j} = 1

for the lone edge

i j

incident to

i

. We will prove that the third property holds.

G A P L P (G, M^{'})

has

n + m^{'}

non-trivial constraints where

n = | J |

and

m^{'} = | M^{'} |

. Since

y

is a basic feasible solution, via the rank lemma, this implies that

| E | = n + m^{'}

. But degree of every

i

and every

j \in M^{'}

is at least

2

. This implies that

\deg (i) = 2

for every

i \in J

and

\deg (j) = 2

for every

j \in M^{'}

and

\deg (j) = 0

for every

j \in M ∖ M^{'}

. Thus

G

consists of a collection of disjoint even cycles. Let

S

be any such cycle. For every job

i \in S

we have sum of

\sum_{j} y_{i j} = 1

; hence

\sum_{i j \in S} y_{i j} = | S | / 2

. Hence there is some machine

j \in S

such that

\sum_{i j} y_{i j} \geq 1

and moreover its degree is exacly two as we argued.

\underline{GAP-Iter-Rounding (G)}

F = \emptyset, M^{'} = M

2. While

(| F | < n)

A. Obtain an optimum basic feasible solution

y

G A P L P (G, M^{'})

B. If there is

i j \in E

such that

y_{i j} = 0

then

G = G - i j

C. Else If there is

i j \in E

such that

y_{i j} = 1

then

F = F \cup {(i j)}, G = G - i, b_{j} = b_{j} - p_{i j}

D. Else If there

j \in M^{'}

such that

d (j) = 1

d (j) = 2

and

\sum_{i} y_{i j} \geq 1

then

M^{'} = M^{'} - j

3. Output assignment

F

Theorem 6.7. Given an instance of GAP that is feasible and has optimum cost $C$ , the algorithm GAP-Iter-Rounding outputs an assignment whose cost is at most $C$ and such that each machine $j$ has load at most $2 b_{j}$ .

The proof is by induction on the number of iterations. Alternatively, it is useful to view the algorithm recursively. We will sketch the proof and leave some of the formal details to the reader (who can also consult ^[4:1]). We observe that the algorithm makes progress in each iteration via Lemma 6.6. The analysis will consider the four cases that can happen in each iteration: (i)

y_{i j} = 0

for some

i j \in E

(ii)

y_{i j} = 1

for some

i j \in E

(iii)

d (j) \leq 1

for some

j \in M^{'}

and (iv)

d (j) = 2

and

\sum_{i j} y_{i j} \geq 1

for some

j \in M^{'}

Thus the algorithm terminates in polynomial number of iterations. It is also not hard to see that

F

corresponds to an assignment of jobs to machines.

Observation 6.8. The algorithm terminates and outputs an assignment of jobs to machines, and job $i$ is assigned to $j$ implies $i j \in E$ .

Now we prove that the assignment has good properties in terms of the cost and loads.

Lemma 6.7. The cost of the LP solution at the start of each iteration is at most $C - \sum_{i j \in F} c_{i j}$ . Hence, at the end of the algorithm the cost of the assignment $F$ is at most $C$ .

Proof. This is true in the first iteration since

F = \emptyset

and the LP cost is less than that of an optimum integer feasible solution. Now consider an iteration assuming that the precondition holds.

y_{i j} = 0

we remove

i j

from

E

and we note that the cost of the LP for the next iteration does not increase since

y

itself is feasible for the residual instance.

y_{i j} = 1

and we add

i j

F

, we can charge the cost of

i j

to what the LP has already paid on the edge

i j

, and the solution

y

with

i j

removed is feasible to the residual instance obtained by removing job

i

and reducing the capacity of

j

b_{j} - p_{i j}

In the other cases we do not change

F

but drop constraints so the LP cost can only decrease in the subsequent iteration.

Now we upper bound the load on each machine

j

Lemma 6.8. For each machine $j, \sum_{i j \in F} p_{i j} \leq 2 b_{j}$ . In fact, a stronger property holds: for each $j$ , its load at the end of the algorithm is at most $b_{j}$ or there is a single job assigned to $j$ such that removing it reduces the load of $j$ to at most $b_{j}$ .

Proof. The proof is by induction on iterations. We will sketch it. Consider a machine

j

. If

y_{i j} = 0

in some iteration we remove

i j

and the load on any machine does not change. If

y_{i j} = 1

we add

i j

F

but for subsequent iterations we reduce

b_{j}

p_{i j}

hence we account for the increase in load of

j

Thus, the only reason why the load of

j

may exceed

b_{j}

is because we drop the load constraint for

j

in some iteration. If we drop it when

d (j) = 1

, then at most one more job can be assigned to

j

and hence its final load can be at most

b_{j} + p_{i j}

for some

i j \in E

. Thus, if

p_{i j} \leq b_{j}

for all

i

the load is at most

2 b_{j}

. We can also drop the constraint for

j

when

d (j) = 2

. However, in this case we have the property that

y_{i_{a}, j} + y_{i_{b}, j} \geq 1

for some two jobs

i_{a}

and

i_{b}

which are the only edges incident to

j

in that iteration. Since

y

was feasible, we also had the constraint that

p_{i_{a} j} y_{i_{a} j} + p_{i_{b} j} y_{i_{b} j} \leq b_{j}^{'}

where

b_{j}^{'}

was the residual capacity of

j

in that iteration. Assume without loss of generality that

p_{i_{a} j} \leq p_{i_{b} j}

; then it follows that

b_{j}^{'} \geq p_{i_{a} j}

. Thus the final load of

j

is at most

b_{j} - b_{j}^{'} + p_{i_{a} j} + p_{i_{b} j}

since both

i_{a}

and

i_{b}

can be assigned to

j

. But this load is at most

b_{j} + p_{i_{b} j} \leq 2 b_{j}

. We leave it to the reader to verify the refined property regarding the load claimed in the lemma.

Running time: The algorithm runs in polynomial number of iterations, and in each iteration it requires an optimum basic feasible solution to the

G A P L P (G, M^{'})

. This can be done in polynomial time. We remark that the algorithm is deliberately described in a simple iterative fashion to make the proof easier. One can speed up the algorithm by considering all the cases together in each iteration. Although iterated rounding is a powerful technique, the running time is typically expensive. Finding faster algorithms that achieve similar guarantees is an open area of research.

6.3 Maximization version of GAP

We consider the maximization version which we refer to Max-GAP. We have

n

items and

m

bins (instead of jobs and machines) where

p_{i j}

is the size of item

i

in bin

j

. Each bin

j

has a capacity

c_{j}

and assigning item

i

to bin

j

yields a profit/weight

w_{i j}

. The goal is to assign items to bins to maximize the weight while not violating any capacities. When

m = 1

we obtain the Knapsack problem.

Multiple Knapsack Problem (MKP): MKP is a special case of Max-GAP in which

w_{i j} = w_{i}

for all

i, j

and

p_{i j} = p_{i}

for all

i, j

. In other words the item characteristics do not depend on where it is assigned to.

Exercise 6.3. Prove that MKP does not admit an FPTAS even for

m = 2

MKP admits a PTAS ^[6] and even an EPTAS ^[7]. Simply greedy algorithms that pack bins one by one using an algorithm for Knapsack as a black box yield a

(1 - 1 / e - ϵ)

and

1 / 2 - ϵ

approximation for MKP when the bins are indentical and when the bins are arbitrary ^[6:1].

In contrast to MKP, Max-GAP does not admit a PTAS. There is an absolute constant

c > 1

such that a

c - ϵ

approximation implies

P = N P

^[6:2]. However, the following is known.

Theorem 6.9. For every fixed $m$ there is a PTAS for Max-GAP.

The preceding theorem can be shown by generalizing the ideas behind the PTAS for Knapsack we discussed in an earlier chapter. An interested reader may try to prove this by considering the case of

m = 2

A $\frac{1}{2}$ -approximation: There is a simple yet clever way to achieve a

\frac{1}{2}

-approximation for Max-GAP via the 2-approximation for the min-cost version that we already saw. Recall that for the min-cost version the algorithm output a solution with cost no more than the optimum cost while violating the capacity of each bin by at most one item. We outline how one can use this to obtain a 2-approximation for Max-GAP and leave the details are an exercise to the reader.

Reduce the exact maximization version to the exact min-cost version in which all items have to be assigned by adding an extra dummy bin.
Use the result for min-cost version to obtain an assignment with weight at least that of the optimum while violating each bin's capacity by at most one item.
Use the preceding assignment to find a feasible packing of items that has profit at least $OPT / 2$ .

For Max-GAP one can use a stronger LP relaxation and obtain a

(1 - 1 / e + δ)

-approximation. We refer the reader to ^[8] for this result, and also to ^[9] for connections to submodular function maximization. The latter connection allows one to obtain an extremely simple

1 / 2 - ϵ

greedy approximation algorithm that is not obvious to discover.

6.4 Bibilographic Notes

The 2-approximation for unrelated machine scheduling is by Lenstra, Shmoys and Tardos ^[10]. The same paper showed that unless

P = N P

there is no

3 / 2 - ϵ

-approximation for unrelated machine scheduling. Bridging this gap has been a major open problem in scheduling. A special case called restricted assignment problem has been extensively studied in this context; in such instances

p_{i j} \in {p_{i}, \infty}

which means that a job specifies the machines it can be assigned to, but its processing time does not vary among the machines it can be assigned to. The

3 / 2

hardness from ^[10:1] applies to restricted assignement problem as well. Svensson ^[11] showed that a strengthend form of LP relaxation (called the configuration LP) has an integrality gap better than 2 for restricted assignment problem but so far there is no polynomial time algorithm to actually output an assignment! The best algorithm that beats 2 for this case runs in quasi-polynomial time ^[12].

As we mentioned Shmoys and Tardos obtained the 2-approximation for GAP. The iterated rounding proof is from ^[4:2].

The approximability of Max-GAP when

m

is not a fixed constant was studied in ^[6:3] although a PTAS for fixed

m

was known quite early ^[13]. The current best approximation ratio is via a configuration LP ^[8:1]. The precise integrality gap of the configuration LP is an interesting open problem.

Vĳay V Vazirani. Approximation algorithms. Springer Science & Business Media, 2013. ↩︎
Alexander Schrĳver. Combinatorial optimization: polyhedra and efficiency. Vol. 24. Springer Science & Business Media, 2003. ↩︎
David B Shmoys and Éva Tardos. “An approximation algorithm for the generalized assignment problem”. In: Mathematical programming 62.1 (1993), pp. 461–474. ↩︎
Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh. Iterative methods in combinatorial optimization. Vol. 46. Cambridge University Press, 2011. ↩︎ ↩︎ ↩︎
Kamal Jain. “A factor 2 approximation algorithm for the generalized Steiner network problem”. In: Combinatorica 21.1 (2001), pp. 39–60. ↩︎
Chandra Chekuri and Sanjeev Khanna. “A polynomial time approximation scheme for the multiple knapsack problem”. In: SIAM Journal on Computing 35.3 (2005), pp. 713–728. ↩︎ ↩︎ ↩︎ ↩︎
Klaus Jansen. “Parameterized approximation scheme for the multiple knapsack problem”. In: SIAM Journal on Computing 39.4 (2010), pp. 1392– 1412. ↩︎
Uriel Feige and Jan Vondrak. “Approximation algorithms for allocation problems: Improving the factor of 1-1/e”. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). IEEE. 2006, pp. 667–676. ↩︎ ↩︎
Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák. “Maximizing a monotone submodular function subject to a matroid constraint”. In: SIAM Journal on Computing 40.6 (2011), pp. 1740–1766. ↩︎
Jan Karel Lenstra, David B Shmoys, and Éva Tardos. “Approximation algorithms for scheduling unrelated parallel machines”. In: Mathematical programming 46.1 (1990), pp. 259–271. ↩︎ ↩︎
Ola Svensson. “Santa claus schedules jobs on unrelated machines”. In: SIAM Journal on Computing 41.5 (2012), pp. 1318–1341. ↩︎
Klaus Jansen and Lars Rohwedder. “A quasi-polynomial approximation for the restricted assignment problem”. In: International Conference on Integer Programming and Combinatorial Optimization. Springer. 2017, pp. 305–316. ↩︎
Ashok K Chandra, Daniel S. Hirschberg, and Chak-Kuen Wong. “Approximate algorithms for some generalized knapsack problems”. In: Theoretical Computer Science 3.3 (1976), pp. 293–304. ↩︎

Approximation Algorithms: Unrelated Machine Scheduling and Generalized Assignment

6.1 Scheduling on Unrelated Parallel Machines

6.2 Generalized Assignment Problem

6.2.1 Shmoys-Tardos Rounding

6.2.2 Iterative Rounding

6.3 Maximization version of GAP

6.4 Bibilographic Notes

Recommended for you

Report Article