Lecture 17: Approximation Algorithms

Lecture 17 Introduction 6.046J Spring 2015 Lecture 17: Approximation Algorithms • Definitions • Vertex Cover • Set Cover • Partition Approximation Algorithms and Schemes Let Copt be the cost of the optimal algorithm for a problem of size n. An approxi­ mation algorithm for this problem has an approximation ratio Q(n) if, for any input, the algorithm produces a solution of cost C such that: max( C Copt , ) ≤ Q(n) Copt C Such an algorithm is called a Q(n)-approximation algorithm. An approximation scheme that takes as input c > 0 and produces a solution such that C = (1 + c)Copt for any fixed c, is a (1 + c)-approximation algorithm. A Polynomial Time Approximation Scheme (PTAS) is an approximation algorithm that runs in time polynomial in the size of the input, n. A Fully Polynomial Time Approximation Scheme (FPTAS) is an approximation algorithm that runs in time polynomial in both n and c. For example, a O(n2/E ) approximation algorithm is a PTAS but not a FPTAS. A O(n/c2 ) approximation algorithm is a FPTAS. Vertex Cover Given an undirected graph G(V, E), find a subset V ' ⊆ V such that, for every edge (u, v) ∈ E, either u ∈ V ' or v ∈ V ' (or both). Furthermore, find a V ' such that |V ' | is minimum. This is an NP-Complete problem. 1 Lecture 17 6.046J Spring 2015 Introduction Approximation Algorithm For Vertex Cover Here we define algorithm Approx Vertex Cover , an approximation algorithm for Ver­ tex Cover. Start with an empty set V ' . While there are still edges in E, pick an edge (u, v) arbitrarily. Add both u and v into V ' . Remove all edges incident on u or v. Repeat until there are no more edges left in E. Approx Vertex Cover runs in poly­ nomial time. Take for example the following graph G: b c d a e f g Approx Vertex Cover could pick edges (b, c), (e, f ) and (d, g), such that V ' = {b, c, e, f, d, g} and |V ' | = 6. Hence, the cost is C = |V ' | = 6. The optimal solution for this example is {b, d, e}, hence Copt = 3. Claim: Approx Vertex Cover is a 2-approximation algorithm. Proof: Let U ⊆ V be the set of all the edges that are picked by Approx Vertex Cover . The optimal vertex cover must include at least one endpoint of each edge in U (and other edges). Furthermore, no two edges in U share an endpoint. Therefore, |U | is a lower bound for Copt . i.e. Copt ≥ |U |. The number of vertices in V ' returned by Approx Vertex Cover is 2 · |U |. Therefore, C = |V ' | = 2 · |U | ≤ 2Copt . Hence C ≤ 2 · Copt . D Set Cover Given a set X and a family of (possibly overlapping) subsets S1 , S2 , · · · , Sm ⊆ X such that ∪m i=1 Si = X, find a set P ⊆ {1, 2, 3, · · · , m} such that ∪i∈P Si = X. Furthermore find a P such that |P | is minimum. Set Cover is an NP-Complete problem. 2 Lecture 17 6.046J Spring 2015 Introduction Approximation Algorithm for Set Cover Here we define algorithm Approx Set Cover , an approximation algorithm for Set Cover. Start by initializing the set P to the empty set. While there are still ele­ ments in X, pick the largest set Si and add i to P . Then remove all elements in Si from X and all other subsets Sj . Repeat until there are no more elements in X. Approx Set Cover runs in polynomial time. In the following example, each dot is an element in X and each Si are subsets of X. S4 S3 S5 S1 S2 S6 Approx Set Cover selects sets S1 , S4 , S5 , S3 in that order. Therefore it returns P = {1, 4, 5, 3} and its cost C = |P | = 4. The optimal solution is Popt = {S3 , S4 , S5 } and Copt = |Popt | = 3. Claim: Approx Set Cover is a (ln(n)+1)-approximation algorithm (where n = |X|). Proof: Let the optimal cover be Popt such that Copt = |Popt | = t. Let Xk be the set of elements remaining in iteration k of Approx Set Cover . Hence, X0 = X. Then: • for all k, Xk can be covered by t sets (from the optimal solution) • one of them covers at least |Xk | t elements • Approx Set Cover picks a set of (current) size ≥ 3 |Xk | t Lecture 17 Introduction 6.046J Spring 2015 • for all k, |Xk+1 | ≤ (1 − 1t )|Xk | (More careful analysis (see CLRS, Ch. 35) relates Q(n) to harmonic numbers. t should shrink.) • for all k, |Xk+1 | ≤ (1 − 1t )k · n ≤ e−k/t · n (n = |X0 |) Algorithm terminates when |Xk | < 1, i.e., |Xk | = 0 and will have cost C = k. e−k/t · n < 1 ek/t > n Hence algorithm terminates when kt > ln(n). Therefore kt = CCopt ≤ ln(n) + 1. Hence Approx Set Cover is a (ln(n) + 1)-approximation algorithm for Set Cover. D Notice that the approximation ratio gets worse for larger problems as it changes with n. Partition The input is a set S = {1, 2, · · · , n} of n items with weights s1 , s2 , · · · , sn . Assume, without loss of generality, that the items are ordered such that s1 ≥ s2 ≥ · · · ≥ sn . � Partition S into sets A and B to minimize max(w(A), w(B)), where w(A) = Si i∈A � and w(B) = Sj . j∈B n � Define 2L = definition. i=1 si = w(S). Then optimal solution will have cost Copt ≥ L by Partition is an NP-Complete problem. Want to find a PTAS (1 + c)-approximation. (Note that 2-approximation in this case is trivial). Also, an FPTAS also exists for this problem. Approximation Algorithm for Partition Here we define Approx Partition. Define m = I 1E l − 1. (c ≈ proceeds in two phases. 1 ) m+1 The algorithm First Phase: Find an optimal partition A' , B ' of s1 , · · · , sm . This takes O(2m ) time. Second Phase: Initialize sets A and B to A' and B ' respectively. Hence they already contain a partition of elements s1 , · · · , sm . Then, for each i, where i goes 4 Lecture 17 Introduction 6.046J Spring 2015 from m + 1 to n, if w(A) ≤ w(B), add i to A, otherwise add i to B. Claim: Approx Partition is a PTAS for Partition. Proof: Without loss of generality, assume w(A) ≥ w(B). Then the approxima­ tion ratio is CCopt = w(A) . Let k be the last item added to A. There are two cases, L either k was added in the first phase, or in the second phase. Case 1: k is added to A in the first phase. This means that A = A' . We have an optimal partition since we can’t do better than w(A' ) when we have n ≥ m items, and we know that w(A' ) is optimal for the m items. Case 2: k is added to A in the second phase. Here we know w(A) − sk ≤ w(B) since this is why k was added to A and not to B. (Note that w(B) may have in­ creased after this last addition to A). Now, because w(A) + w(B) = 2L, w(A) − sk ≤ w(B) = 2L − w(A). Therefore w(A) ≤ L + s2k . Since s1 ≥ s2 ≥ · · · ≥ sn , we can say that s1 , s2 , · · · , sm ≥ sk . Now since k > m, 2L ≥ (m + 1)sk . L + s2k sk sk 1 Now, ≤ = 1+ 2L ≤ 1+ (m+1)·s = 1+ m+1 = 1+c. Hence Approx Partition k L is a (1 + c)-approximation for Partition. D w(A) L 5 Lecture 17 6.046J Spring 2015 Introduction Natural Vertex Cover Approximation Here we describe Approx Vertex Cover Natural , a different approximation algorithm for Vertex Cover. Start with an empty set V ' . While there are still edges left in E, pick the vertex v ∈ V that has maximum degree and add it to V ' . Then remove v and all incident edges from E. Repeat until no more edges left in E. In the end, return V ' . The following example shows a bad-case example for Approx Vertex Cover Natural . In the example, the optimal cover will pick the k! vertices at the top. k! vertices of degree k ... k!/k vertices of degree k k!/(k-1) vertices of degree k-1 k! vertices of degree 1 Approx Vertex Cover Natural could possibly pick all the bottom vertices from left 1 to right in order. Hence the cost could be k! · ( k1 + k−1 + · · · + 1) ≈ k! log k. Which is a factor of log k worse than optimal. Claim: Approx Vertex Cover Natural is a (log n)-approximation. Proof: Let Gk be the graph after iteration k of the algorithm. And let n be the number of edges in the graph, i.e. |G| = n = |E|. With each iteration, the algorithm selects a vertex and deletes it along with all incident edges. Let m = Copt be the number of vertices in the optimal vertex cover for G. Then let’s look at the first m iterations of the algorithm: G0 → G1 → G2 → · · · → Gm . Let di be the degree of the maximum degree vertex of Gi−1 . Then the algorithm deletes all edges incident on that vertex to get Gi . Therefore: |Gm | = |G0 | − m � i=1 6 di Lecture 17 6.046J Spring 2015 Introduction Also: m � di ≥ i=1 m � |Gi−1 | i=1 m This is true because given |Gi−1 | edges that can be covered by m vertices, we know i−1 | that there is a vertex with degree at least |Gm . Then: m � |Gi−1 | i=1 m ≥ m � |Gm | i=1 m = |Gm | This is true since |Gi | ≤ |Gi−1 | for all i. Then, it follows: |G0 | − |Gm | ≥ |Gm | Because |Gm | ≤ m � i=1 di . Hence after m iterations, the algorithm will have deleted half or more edges from G0 . And generally, since every m iterations it will halve the number of edges in the graph, in m · log |G0 | iterations, it will have deleted all the edges. And since with each iteration it addes 1 vertex to the cover, it will end up with a vertex cover of size m · log |G0 | = m · log n. Since we assumed that m was the size of n the optimal vertex cover, CCopt = m log = log n. Hence Approx Vertex Cover Natural m is a (log n)-approximation. D Note that since n ≈ k! log k in the example of Figure , the worst-case example is log k ≈ log log n worse, but we have only shown an O(log n) approximation. 7