Approximation Algorithms
2021-03-31 CSC373 Winter 2021 – Sam Toueg 1
So far, we have seen approximation algorithms for: • Δ-TSP (Euclidian Traveling Salesman Problem)
ØUsing MST
• Minimum Vertex cover
ØUsing Greedy algorithm and Matching • Minimum Weighted Vertex Cover
ØUsing ILP: Relaxation and Rounding
2021-03-31 CSC373 Winter 2021 – Sam Toueg 2
Makespan Minimization
2021-03-31 CSC373 Winter 2021 – Sam Toueg 3
Makespan
• Problem
Ø Input: 𝑚 identical machines, 𝑛 jobs,
job 𝑗 requires processing time 𝑡!
Ø Output: Assign jobs to machines to minimize makespan
Ø Constraints:
o Each job must run contiguously on one machine
o Each machine can process at most one job at a time
ØLet𝑆𝑖 =setofjobsassignedtomachine𝑖 ØLoadonmachine𝑖:𝐿” =∑!∈$ ” 𝑡!
Ø Goal: minimize makespan 𝐿 = max 𝐿” ”
2021-03-31 CSC373 Winter 2021 – Sam Toueg 4
Makespan
• Even the special case of 𝑚 = 2 machines is NP-hard!
• Proof: by reduction from PARTITION
• PARTITION
Ø Input: Multiset of integers 𝑆
Ø Output: Can we partition 𝑆 into two sets with equal sum?
o PARTITION is NP-complete (we proved this)
o Reduce PARTITION to MAKESPAN (easy exercise):
2021-03-31 CSC373 Winter 2021 – Sam Toueg 5
Makespan
• Greedy algorithm:
Ø Consider the 𝑛 jobs in some “nice” sorted order
Ø Assign each job 𝑗 to a machine with the smallest load so far
• Note
Ø Implementable in 𝑂 𝑛 log 𝑚 using priority queue (min Heap)
• Back to greedy…?
Ø But this time, we can’t hope that greedy will be optimal Ø We can still hope that it is “approximately’’ optimal
• Which order?
2021-03-31 CSC373 Winter 2021 – Sam Toueg 6
Makespan
• Theorem [Graham 1966]
Ø Regardless of the order, greedy gives a 2-approximation
• 𝐿 = makespan found by greedy algo
• 𝐿∗ = optimal makespan
• Theorem says that 𝐿 ≤ 2𝐿∗
• To prove this, we first show 𝐿∗ is not too small
2021-03-31 CSC373 Winter 2021 – Sam Toueg 7
Makespan
• Theorem [Graham 1966]
Ø Regardless of the order, greedy gives a 2-approximation
• Fact 1: 𝐿∗ ≥ max 𝑡” ”
Ø Some machine must process job with highest processing time • F a c t 2 : 𝐿 ∗ ≥ $# ∑ ” 𝑡 ”
Ø Total processing time is ∑! 𝑡!
Ø At least one of the 𝑚 machines must do
at least 1/𝑚 of this work (pigeonhole principle)
2021-03-31 CSC373 Winter 2021 – Sam Toueg 8
• Theorem [Graham 1966]
Ø Regardless of the order, greedy gives a 2-approximation.
R e c a l l : 1 𝐿 ∗ ≥ m a x 𝑡 ” a n d ( 2 ) 𝐿 ∗ ≥ $# ∑ ” 𝑡 ” ”
• Proof:
Ø Suppose machine 𝑖 is bottleneck under greedy (so 𝐿 = 𝐿” )
Ø Let 𝑗∗ = last job assigned to machine 𝑖 by greedy
Ø Right before 𝑗∗ was assigned to 𝑖: oTheloadonmachine𝑖was𝐿′! =𝐿! −𝑡”∗
o This was the smallest load among all the machines: 𝐿! − 𝑡”∗ ≤ 𝐿′#, ∀𝑘
Ø After this assignment, the machine loads 𝐿′& can only increase. So at the end of the greedy algorithm, we have:
most loaded machine at the end of the greedy algorithm
o𝐿!−𝑡”∗ ≤𝐿# o𝑚(𝐿! −𝑡”∗)≤∑#𝐿# o𝑚(𝐿! −𝑡”∗)≤∑”𝑡”
o 𝐿 ! − 𝑡 ” ∗ ≤ %$ ∑ ” 𝑡 ”
∀𝑘,1≤𝑘≤m (bysummingoverall𝑘,1≤𝑘≤m)
(because∑#𝐿# =∑”𝑡”)
Fact 1
𝐿 = 𝐿” ≤ 2𝐿∗
remember:
o 𝐿 ! ≤ 𝑡 ” ∗ + %$ ∑ ” 𝑡 ” ≤ 𝐿 ∗ + 𝐿 ∗ = 2 𝐿 ∗ S o :
𝐿” ≤ 𝑡!∗ + 𝐿∗ CSC373 Winter 2021 – Sam Toueg Fact 2
9
Makespan (on-line)
• We proved:
Theorem: Regardless of the order,
greedy gives a 2-approximation
By improving the analysis, Graham proved the greedy algorithm
is actually a bit better:
• Theorem [1966]: Regardless of the order,
greedy gives a (2 − $# )-approximation
• Is this tight?
Yes: There is an example where greedy does perform this badly
2021-03-31 CSC373 Winter 2021 – Sam Toueg 11
• Worst-case example for greedy algorithm: Ø𝑚 𝑚−1 jobsoflength1each
Ø one job of length 𝑚
• Greedy assignment: (example for 𝑚 = 4)
Makespan: 𝑚−1 +𝑚=2𝑚 −1
𝑚
𝑚−1
𝑚 Here 𝑚 = 4
Idea: keeping long jobs at the end seems bad. So start with them first!
Makespan: 𝑚
Greedy/Optimal = ‘%($ = 2 − $ %%
• Optimal assignment: 𝑚
2021-03-31 𝑚 CSC373 Winter 2021 – Sam Toueg
13
Makespan (off-line)
• Longest Processing Time (LPT) First
Ø Run the greedy algorithm but consider jobs in
decreasing order of length
• To show this performs better, we need more facts
about the optimal solution 𝐿∗ most loaded machine
• Fact 3: If the bottleneck machine has only one job, then the solution is optimal.
Why?
Ø The optimal solution must assign that job to some machine!
2021-03-31 CSC373 Winter 2021 – Sam Toueg 14
Makespan (off-line)
• Longest Processing Time (LPT) First
Ø Run the greedy algorithm but consider the 𝑛 jobs in
decreasing order of length ØSuppose𝑡: ≥𝑡; ≥⋯≥𝑡<
•Fact4:Iftherearemorethan𝑚jobs,𝐿∗ ≥2⋅𝑡$6# (and so 𝑡$6# ≤ 7∗)
Proof: 8
ØConsider the first 𝑚 + 1 jobs (lengths 𝑡: ≥ 𝑡; ≥ ⋯ ≥ 𝑡=>:) Ø Each one of these jobs requires at least 𝑡=>: time
Ø Since there are 𝑚 + 1 of them and only 𝑚 machines, by pigeonhole principle, at least two of them will end up on the same machine (in any solution, including the optimal one)
Ø So the final load on that machine is ≥ 2 ⋅ 𝑡=>:
2021-03-31 CSC373 Winter 2021 – Sam Toueg 15
• Theorem: Greedy with longest processing time first gives a 3/2-approximation
• Proof: (Similar to the proof for arbitrary ordering)
Ø Consider the bottleneck machine 𝑖 (so makespan is 𝐿 = 𝐿” )
Ø Let 𝑗∗ be the last job that greedy assigned to machine 𝑖 Ø Case 1: Machine 𝑖 has only one job (namely, job 𝑗∗)
o By Fact 3, greedy is optimal in this case (i.e., 𝐿 = 𝐿∗) Ø Case 2: Machine 𝑖 has at least two jobs
oGreedyfirstassignsjobs1,2,…,𝑚withlengths𝑡$ ≥𝑡’ ≥⋯≥𝑡% to machines 1, 2, … , 𝑚 (one job per machine)
o Since 𝑗∗ is not the first job given to machine 𝑖, 𝑗∗ ≥ 𝑚+1 oSo𝑡”∗ ≤𝑡%)$
oByFact4:𝑡%)$≤ *∗ . So𝑡”∗ ≤ *∗ ”∗
o We previously proved (for greedy with arbitrary ordering): 𝐿! ≤ 𝑡”∗ + 𝐿
o 𝐿 = 𝐿! ≤ 𝑡”∗ + 𝐿∗ ≤ 𝐿∗ + 𝐿∗ = 1.5 𝐿∗ So: 2
2021-03-31 CSC373 Winter 2021 – Sam Toueg 16
𝐿 ≤ 1.5𝐿∗
We proved:
• Theorem: Greedy with LPT rule gives a 3/2-approximation
Ø Is our analysis tight? No!
• Theorem [Graham 1966]: Greedy with LPT rule gives
a (? − : )-approximation @ @=
Ø Is this tight?
o Yes: the greedy-LPT approximation can indeed be as bad as + − $
Ø Tight example: , ,% o2jobsoflengths𝑚, 2oflengths𝑚+1,…,2oflengths2𝑚−1
and one more job of length 𝑚
o Greedy-LPT has makespan 4𝑚 − 1 (verify!) o Optimal solution has makespan 3𝑚 (verify!)
o Thus, approximation ratio here is +%($ = + − $ ,% , ,%
2021-03-31 CSC373 Winter 2021 – Sam Toueg 19
1
5=𝑚
7
9 = 2𝑚 −
9
8
8
6
6
7
5=𝑚
5
𝑚=5
• Worst-case example for greedy-LPT algorithm:
o 2 jobs of lengths 𝑚, 𝑚 + 1, … , 2𝑚 − 1, one more job of length 𝑚
• Greedy assignment (example for 𝑚 = 5)
Makespan:4𝑚 −1
• Optimal assignment: 𝑚=5
Makespan: 3𝑚
Greedy/Optimal = %$&# =4−1 ‘$
3 3𝑚
5
5
5
6
9
6
9
7
8
7
8
2021-03-31
CSC373 Winter 2021 – Sam Toueg
20