CS计算机代考程序代写 algorithm Approximation Algorithms

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