程序代写代做代考 algorithm CSC373H Lecture 9

CSC373H Lecture 9
Dan Zingaro
November 14, 2016

Vertex Cover
􏹩 A vertex cover of undirected graph G = (V,E) is a set of vertices X such that, for any edge (u,v) in E, u ∈ X or v∈X
􏹩 That is, it’s a set of vertices such that each edge has at least one of its endpoints in the set
􏹩 The size of a vertex cover is the number of vertices in it
􏹩 The vertex cover problem is to find a vertex cover of minimum size

Vertex Cover: Examples
1. What is the minimum vertex cover of this graph?
a
bcdef
2. A clique is a graph that has an edge connecting every pair of vertices. What is the minimum vertex cover in the n-node clique?

NP-Complete Problems
􏹩 Unfortunately, vertex cover is what is known as an NP-complete problem
􏹩 NP-complete problems are problems for which no exact polynomial-time algorithm is known
􏹩 Many believe that no polynomial-time algorithm will ever be found for these problems
􏹩 So, rather than search for an implausible exact, polynomial algorithm, one approach is to study approximation algorithms
􏹩 …andwecanuseourexistingalgorithmdesigntechniquesto design these approximation algorithms!

Approximation Ratios
􏹩 Let C be the solution returned by our algorithm and C∗ be the optimal solution
􏹩 Vertex cover is a minimization problem: we want to minimize a quantity (number of vertices)
􏹩 We say that an algorithm for a minimization problem has approximation ratio r if |C|/|C∗| ≤ r
􏹩 We can do analogously for a maximization problem, where the goal is to maximize a quantity

Greedy Algorithm for Vertex Cover
The algorithm is fast. But how good is it?
C = {} # vertex cover F=E
while F != {}:
let (u, v) be some edge in F
C = C + {u, v}
remove from F any edge incident to u or v
return C

Greedy Algorithm: Approximation Ratio Proof
Theorem: the greedy algorithm is a 2-approximation algorithm for vertex cover.
􏹩 C is a vertex cover, because the algorithm removes only covered edges from F until F is empty
􏹩 Let A denote the edges (u,v) chosen by the algorithm
􏹩 Let C∗ be an optimal vertex cover
􏹩 Any vertex cover, including C∗, must include at least one endpoint of each edge in A
􏹩 No two edges in A share an endpoint
􏹩 Therefore, number of vertices in C∗ must be ≥ number of edges in A

Greedy Algorithm: Approximation Ratio Proof…
􏹩 From previous slide, we have |C∗| ≥ |A|
􏹩 As each edge in A results in two vertices added to C, we also have |C| = 2|A|
|C| = 2|A| ≤ 2|C∗|

Back to Knapsack
􏹩 Recall the 0-1 knapsack problem that we studied
􏹩 We gave a dynamic-programming algorithm whose runtime was O(nW), where n is the number of items and W is the knapsack weight
􏹩 Unfortunately, this is not a polynomial-time algorithm
􏹩 We want a big-oh bound in terms of the size of the input
􏹩 However, W is not the size of the integer W
􏹩 Instead, log2 W is the size of integer W (number of bits required to represent W )

Back to Knapsack…
􏹩 Letx=log2W bethesizeofW
􏹩 Then,W=2x
􏹩 So, our algorithm is O(n2x), which is not polynomial in x
􏹩 In fact, 0-1 knapsack is NP-complete, so we suspect that there is no polynomial-time exact algorithm
􏹩 Buttherearepolynomial-timeapproximationalgorithms…

Greedy Algorithm for Knapsack
The algorithm is fast. But how good is it?
sort the items by decreasing v_i/w_i
for each item:
if the item fits in the knapsack, add it
otherwise, stop the algorithm

Greedy Algorithm: Arbitrarily Bad
􏹩 Knapsack is an example of a maximization problem
􏹩 The given greedy algorithm has no finite approximation ratio
􏹩 That is, we can make the approximation ratio arbitrarily bad
􏹩 e.g. considerW =1000,w1 =2,v1 =2,w2 =1000, v2 = 999
􏹩 The greedy algorithm yields only 2/1000 of the optimal value!
􏹩 The algorithm is therefore not useful as-is