Approximation Algorithms
2021-03-24 CSC373 Winter 2021 – Sam Toueg 1
NP-Completeness
• We saw that many problems are NP-complete
Ø Unlikely to have polynomial time algorithms to solve them Ø What can we do?
• One idea:
Ø Instead of solving them exactly, solve them approximately
2021-03-24 CSC373 Winter 2021 – Sam Toueg 2
Approximation Algorithms
• We’ll focus on optimization problems Ø Decision problem: “Is there…where…≥ “?”
o “Is there a clique of size ! in a given graph “?”
o “Is there an assignment which satisfies at least ! clauses of a given
formula #?”
Ø Optimization problem: “Find…that maximizes…”
o “Find a clique of maximum size in a given graph “.’’
o “Find an assignment which satisfies the maximum possible number of
clauses from a given formula #.” Ø If the decision problem is hard,
then the corresponding optimization problem is also hard
2021-03-24 CSC373 Winter 2021 – Sam Toueg 4
Approximation Algorithms
• There is a function !”#$ we want to minimize, or
a function %&”‘($ we want to maximize
• Given input instance )…
Ø !”# $ : solution returned by our algorithm
Ø 234 $ : optimal solution that minimizes 5678, or maximizes 3:6;<8
Ø Then, the approximation ratio of !"# on instance $ is: !"#$ %&' ( or *,"-.$ )*+ (
!"#$ )*+ ( *,"-.$ %&' (
Ø E.g., 2-approximation = twice the optimal cost or
half the optimal profit
2021-03-24 CSC373 Winter 2021 - Sam Toueg 5
Approximation Algorithms
• Approximation ratio of *+, on instance ) is
!"#$ %&' ( or *,"-.$ )*+ ( !"#$ )*+ ( *,"-.$ %&' (
Ø Note: These are defined to be ≥ 1 in each case
• *+, has worst-case --approximation if for every instance ) of the problem:
Ø!"#$ %&' ( Ø-/"01$ %&' (
≤*⋅!"#$ ,-. ( or ≥!" ⋅-/"01$ ,-. (
2021-03-24
CSC373 Winter 2021 - Sam Toueg 7
Traveling Salesman Problem
2021-03-24 CSC373 Winter 2021 - Sam Toueg 3
But first a quick reminder of ... Minimum Spanning Tree (MST)
2021-03-24 CSC373 Winter 2021 - Sam Toueg 4
Tree
• A tree is a connected undirected graph with no cycles
2021-03-24 CSC373 Winter 2021 - Sam Toueg 5
Spanning Tree of a graph
• ! = ($, &): an undirected connected graph
• Spanning tree of !: tree ) that connects (i.e., ``spans’’) all the nodes of !
)=($,&′)with&′ ⊆ & 121212
73673673
45454
6
5
2021-03-24
CSC373 Winter 2021 - Sam Toueg
6
! "1
"2
Minimum Spanning Tree (MST) of a graph
• ! = ($, &) : a weighted undirected connected graph
• The weight of a spanning tree ) of ! is the total weight of its edges
4
BA4BABAB 131313313123
A
AB
32 D2C
DCDCD2C
! "0 "1 "2 "3
DC
2021-03-24 #(") = 8 #(") = 6 7 0 #("1) = 7 2 #("3) = 6
Minimum Spanning Tree (MST) of a graph
• ! = ($, &) : a weighted undirected connected graph
• The weight of a spanning tree ) of ! is the total weight of its edges
• A minimum spanning tree of ! is a minimum-weight spanning tree of !
4
32 D2C
!
2021-03-24
BA4BABAB 131313313123
A
AB
DCDCD2C
DC
MST "3 #("3) = 6
"0
#(") = 8 0
Not MST
"1 #("1) = 7
"2
#(") = 6 2
8
Minimum Spanning Tree (MST) of a graph
• Fact (learned in csc263):
Given any weighted graph ! with , nodes and - edges we can find an MST of ! in .(- log ,)-time
(e.g., by running Kruskal’s or Prim’s greedy algorithms)
2021-03-24 CSC373 Winter 2021 - Sam Toueg 9
TSP: Traveling Salesman Problem
•Input:Undirectedcompletegraph!= $,&
with non-negative edge costs (also called weights)
• Output: a tour of ! of minimum total edge cost (called TSP tour) Tour: Cycle that visits every node of ! exactly once
a tour of ! a TSP Tour of ! 44
32323112
!
• • •
Brute-force algo: find all tours of !, select the min cost one. But this takes exponential time.
TSP is NP-hard! (we are not going to show this.)
So is unlikely that a polynomial time algorithm for TSP exists.
11
55
Cost: 7
Cost: 14
2021-03-24 CSC373 Winter 2021 - Sam Toueg 10
A simpler version of the TSP Problem: Δ-TSP
• Assume the edge costs satisfy the triangle inequality, denoted Δ – inequality:
• Assume the weights/costs satisfy the triangle inequality Øforallnodes+,-,#of!: . +,- ≤. +,# +. #,- [*]
*
• Δ – inequality: Ø Examples:
"(*, %) "(#, %) %
"(#, *) • Nodes of ! are points on a Euclidian plane, e.g. cities on a map #
• ∀nodes+,-,#of!:. +,- ≤. +,# +. #,- [*] • Nodes of ! are points on a Euclidian plane, e.g. cities on a map
• Examples:
• " #, % = Euclidean distance between # and %
• counter-example: airline prices!
• " #, % = Euclidean distance between # and %
• Suppose we consider only !s that satisfy [*]. • Δ-TSP (simpler version of TSP):
!",$ ≤!",& +!&,$
• Non-example: airline prices!
• We now consider only weighted graphs that satisfy [*]
• Is the TSP problem easier to solve? (We now call this problem Δ-TSP) •Input:Undirectedcompletegraph!= 1,2
• Facts: with non-negative edge costs that satisfy the Δ – inequality
1. Δ-TSP is still NP-Complete, but...
• Output: a tour of ! of minimum total edge cost (called TSP tour)
2. We can find an approximate solution to Δ-TSP efficiently: There is a polytime algo that finds a tour of ! whose cost is within a fixed constant factor of the optimal tour!
• Is Δ-TSP easier to solve than TSP?
2021-03-24 CSC373 Winter 2021 - Sam Toueg 11
A simpler version of the TSP Problem: Δ-TSP
• Δ-TSP (simpler version of TSP):
≤# $,& +# &,! [*] • Input:Undirectedcompletegraph!= 1,2
# $(!, #)
$(#, ")
! $(!,") " $!," ≤$!,# +$#,"
e triangle inequality
with non-negative edge costs that satisfy the Δ – inequality [*]. • Output: a tour of ! of minimum total edge cost (called TSP tour)
ow call this problem Δ-TSP)
mate solution to Δ-TSP efficiently: There is a polytime algo that finds a tour of $ whose cost is within a fixed constant factor of the optimal tour!
te, but... • Is Δ-TSP easier to solve than TSP?
points on a Euclidian plane, e.g. cities on a map lidean distance between ! and "
airline prices!
1. Bad news: Δ-TSP is still NP-hard (we will not show this)
2. Good news: We can find an approximate solution to Δ-TSP efficiently:
There is a polynomial-time algorithm that finds a tour of ! whose cost is within a fixed constant factor of the optimal (i.e., min-cost) TSP tour!
• We will now give such an approximation algorithm for Δ-TSP
• To do so, we first need a brief reminder about Minimum Spanning Trees... 2021-03-24 CSC373 Winter 2021 - Sam Toueg 12
h
e
e
Cost of TSP versus Cost of Minimum Spanning Tree
Lemma: Let )34 be an optimal (i.e. min-cost) tour of ! Let 53) be a minimum spanning tree of ! Then: c789 53) ≤ ;789()34)
Proof:
Consider any "45 of !:
e
a TSP of (
a ST of (
Remove any edge 6 of "45. Clearly: .789 4" ≤ .789 "45 Since: .789 :4" ≤ .789 4"
We get: .789 :4" ≤ .789("45) 2021-03-24
This gives some spanning tree 4" of ! (by definition of a minimum spanning tree)
CSC373 Winter 2021 - Sam Toueg 13
An approximation algorithm for Δ-TSP
Given any graph ! with edge weights (we omit the edge weights in this illustration)
1.
5 7
6
4 3
2
1
8
2021-03-24
CSC373 Winter 2021 - Sam Toueg
14
An approximation algorithm for Δ-TSP
Find an 53) of !
This can be done in <(= log A)-time
by a greedy algorithm, like Kruskal’s or Prim’s algorithm
1.
5 7
6
4 3
2
1
8
2021-03-24
CSC373 Winter 2021 - Sam Toueg
15
An approximation algorithm for Δ-TSP 1. Find an 53) of !
5 7
6
4 3
2
1
8
2021-03-24
CSC373 Winter 2021 - Sam Toueg
16
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice
5 7
6
4 3
2
1
8
2021-03-24
CSC373 Winter 2021 - Sam Toueg
17
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:1 7
5
3
6
8
4
B
2
1
start at some node
2021-03-24
CSC373 Winter 2021 - Sam Toueg
18
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:12 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
19
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:123 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
20
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:1234 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
21
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:12343 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
22
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:123435 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
23
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:1234353 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
24
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:12343532 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
25
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:123435326 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
26
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:1234353267 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
27
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:12343532676 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
28
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:123435326768 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
29
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:1234353267686 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
30
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:12343532676862 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
31
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:123435326768621 7
5
3
6
8
4
B
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
32
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:123435326768621 7
5
3
6
.789 B =2 ∗.789 :4"
(*)
4
B
2
1
8
2021-03-24
CSC373 Winter 2021 - Sam Toueg
33
An approximation algorithm for Δ-TSP
2. Do a full walk of the 53) : this gives a cycle
< of ! that uses each edge of 53) twice B:123435326768621 7
.789 B =2 ∗.789 :4" (*)
Note: B is a cycle of ! but it is not a tour of !:
B revisits some nodes (like 3) several times
8
5
3
6
4
B
2
1
2021-03-24 CSC373 Winter 2021 - Sam Toueg
34
An approximation algorithm for Δ-TSP 3. Transform < into a tour <∗ of ! by using
shortcuts to remove repeated nodes B:123435326768621 7
5
3
6
.789 B =2 ∗.789 :4"
(*)
4
B
2
1
8
2021-03-24
CSC373 Winter 2021 - Sam Toueg
35
An approximation algorithm for Δ-TSP 3. Transform < into a tour <∗ of ! by using
shortcuts to remove repeated nodes B:123435326768621 7
5
3
6
4
.789 B =2 ∗.789 :4"
(*)
B∗
8
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
36
An approximation algorithm for Δ-TSP 3. Transform < into a tour <∗ of ! by using
shortcuts to remove repeated nodes B:123435326768621 7
5
3
6
4
.789 B =2 ∗.789 :4"
(*)
B∗
8
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
37
An approximation algorithm for Δ-TSP 3. Transform < into a tour <∗ of ! by using
shortcuts to remove repeated nodes B:123435326768621 7
5
3
6
4
.789 B =2 ∗.789 :4"
(*)
B∗
8
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
38
An approximation algorithm for Δ-TSP 3. Transform < into a tour <∗ of ! by using
shortcuts to remove repeated nodes B:123435326768621 7
5
3
6
4
.789 B =2 ∗.789 :4"
(*)
B∗
8
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
39
An approximation algorithm for Δ-TSP 3. Transform < into a tour <∗ of ! by using
shortcuts to remove repeated nodes B:123435326768621 7
node 3 is repeated in *
5
3
2
1
4
.789 B =2 ∗.789 :4"
(*)
6
B∗
8
2021-03-24
CSC373 Winter 2021 - Sam Toueg
40
An approximation algorithm for Δ-TSP 3. Transform < into a tour <∗ of ! by using
shortcuts to remove repeated nodes B:123435326768621 7
bypass node 3: go to 5 directly
5
3
4
.789 B =2 ∗.789 :4"
(*)
6
B∗
8
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
41
An approximation algorithm for Δ-TSP 3. Transform < into a tour <∗ of ! by using
shortcuts to remove repeated nodes B:123435326768621 7
By Δ-inequality of edge weights: going 4à5 directly is cheaper than going 4à3à5
5
3
4
.789 B =2 ∗.789 :4"
(*)
6
B∗
8
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
42
An approximation algorithm for Δ-TSP 3. Transform < into a tour <∗ of ! by using
shortcuts to remove repeated nodes B:123435326768621 7
5
3
6
4
.789 B =2 ∗.789 :4"
(*)
B∗
8
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
43
An approximation algorithm for Δ-TSP 3. Transform < into a tour <∗ of ! by using
shortcuts to remove repeated nodes B:123435326768621 7
5
3
6
4
.789 B =2 ∗.789 :4"
(*)
B∗
8
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
44
An approximation algorithm for Δ-TSP 3. Transform < into a tour <∗ of ! by using
shortcuts to remove repeated nodes B:123435326768621 7
5
3
6
4
.789 B =2 ∗.789 :4"
(*)
B∗
8
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
45
An approximation algorithm for Δ-TSP 3. Transform < into a tour <∗ of ! by using
shortcuts to remove repeated nodes B:123435326768621 7
5
3
6
4
.789 B =2 ∗.789 :4"
(*)
B∗
8
2
1
2021-03-24
CSC373 Winter 2021 - Sam Toueg
46
An approximation algorithm for Δ-TSP 3. Transform < into a tour <∗ of ! by using
shortcuts to remove repeated nodes B:123435326768621 7
5
3
6
4
.789 B =2 ∗.789 :4" (*) B∗ =123456781
By Δ-inequality of edge weights: .789 B∗ ≤ .789 B (**)
B∗
8
2
1
By (*) and (**) above: .789 B∗ ≤ 2 ∗ .789(:4") Recall (Core Lemma): .789 :4" ≤ .789("45) So: .789 B∗ ≤ 2 ∗ .789("45)
The cost of the tour B∗ found this algo is at most twice the cost of a TSP tour of ! 2021-03-24 CSC373 Winter 2021 - Sam Toueg 47