6.046J Lecture 18: Polynomial-Time Approximations

Lecture 18 Polynomial-Time Approximations Supplemental reading in CLRS: Chapter 35 except §35.4 If you try to design algorithms in the real world, it is inevitable that you will come across NP-hard problems. So what should you do? 1. Maybe the problem you want to solve is actually less general than the NP-hard problem. • Perhaps the input satisfies certain properties (bounded degree, planarity or other geometric structure, density/sparsity. . . ) • Remember, if you are able to reduce your problem to an NP-hard problem, that doesn’t mean your problem is NP-hard—it’s the other way around! 2. Maybe you can settle for an approximation. 3. Maybe an exponential algorithm is not so bad. • There might be an O (c n ) algorithm with c ≈ 1. In this lecture we will focus on item 2: approximation algorithms. As the name suggests, an approximation algorithm is supposed to return an answer that is close to the correct answer. There are several types of approximations one might consider, each based on a different notion of closeness. Definition. Suppose A is an algorithm for the optimization problem Π. (So the answer to Π is a number which we are trying to maximize or minimize, e.g., the weight of a spanning tree.) Given input x, we denote the output of A by A(x), and the optimal answer by Π(x). The following are senses in which A can be an “approximation algorithm” to the problem Π: • The most common type of approximation is multiplicative. For a positive number α ∈ R (which may depend on the input), we say that A is a multiplicative α-approximation (or simply an α-approximation) to Π if, for every input x, ½ ¾ αΠ(x) ≤ A(x) ≤ Π(x) if Π is a maximization problem . Π(x) ≤ A(x) ≤ αΠ(x) if Π is a minimization problem Of course, we must have 0 < α ≤ 1 for a maximization problem and α ≥ 1 for a minimization problem. If someone talks about a “2-approximation” to a maximization problem, they are probably referring to what here would be called a 21 -approximation. • For a positive number β ∈ R, we say that A is a additive β-approximation to Π if, for every input x, Π(x) − β ≤ A(x) ≤ Π(x) + β. • There are lots of other possibilities.1 There is no need to worry about memorizing different definitions of approximation. When someone talks about an “approximation,” it is their job to define precisely in what way it approximates the answer. In this lecture we will see approximation algorithms for three NP-hard problems: Problem Vertex Cover Set Cover Partition Approximation factor 2 ln n + 1 (where n is the total number of elements) 1 + ² for any given parameter ² > 0 Note that the (1 + ²)-approximation algorithm to Partition is a so-called polynomial-time approximation scheme (PTAS). Given a parameter ² > 0, the PTAS generates a polynomial-time algorithm which approximates the Partition problem to a factor of 1 + ². Naturally, the polynomials will get larger as we decrease ², since we are asking for a better approximation. The approximations to Vertex Cover and Set Cover in this lecture are conjectured to be optimal, in the sense that giving a better approximation would be NP-hard.2,3 There exist better approximations to Partition, though.4 18.1 Vertex Cover NP-hard problem (Vertex Cover). Given an undirected graph G = (V , E), a vertex cover of G is a subset V 0 ⊆ V such that, for every edge (u, v) ∈ E, we have either u ∈ V 0 or v ∈ V 0 . The Vertex Cover problem asks, given a graph G, what is the smallest possible vertex cover? Approximation Algorithm: 1 2 3 4 5 6 V0 ← ; while E is nonempty do Pick any (u, v) ∈ E V 0 ← V 0 ∪ { u, v} Remove from E all edges touching u or v Remove u and v from V 1 As a final example, we might combine multiplicative and additive approximations to define an “α, β–affine-linear approximation,” in which α−1 Π(x) − β ≤ A(x) ≤ αΠ(x) + β for all inputs x, where α ≥ 1. 2 If the so-called “Unique Games Conjecture” holds, then it is NP-hard to α-approximate Vertex Cover for any constant α < 2. It was recently proved that it is NP-hard to (c ln n)-approximate Set Cover for any constant c < 1. 3 Proofs of such optimality typically use the probabilistically checkable proofs (PCP) theorem. The PCP theorem states that a problem is in NP if and only if solutions to the problem can be verified (with high probability) by a certain kind of randomized algorithm. 4 There exists a PTAS for Partition in which the running time depends only polynomially on 1/²; this sort of PTAS is known as a fully polynomial-time ¡ ¢approximation scheme (FPTAS). As a consequence, for any given integer r there exists a polynomial-time 1 + 1/n r -approximation to Partition. Moreover, there exists a pseudo-polynomial–time algorithm which solves the Partition problem exactly. A pseudo-polynomial–time algorithm is one whose running time is polynomial in the size of the input and the numeric value of the output (in this case, the “cost” of the optimal partition). Lec 18 – pg. 2 of 6 Figure 18.1. Example run of the approximation algorithm for Vertex Cover. The edges chosen by line 3 are highlighted in orange and the chosen vertices are circled. The algorithm returns a cover of size 4, whereas the optimal covering has size 3. Figure 18.2. The Set Cover problem gives us a covering of a universe set U and asks us to find a small subcovering. How many of the sets in this picture are required to cover the array of dots? It is clear that this algorithm always returns a vertex cover. Moreover, if G is given in the adjacency-list format, then the algorithm runs in linear time. Claim. The cover returned by this algorithm is at most twice the size of an optimal cover. Proof. Let E 0 denote the set of edges that get chosen by line 3. Notice that no two edges in E 0 share an endpoint. Thus, every vertex cover must contain at least one endpoint of each edge in E 0 . Meanwhile, the output of our algorithm consists precisely of the two endpoints of each edge in E 0 . 18.2 Set Cover NP-hard problem (Set Cover). Given a set U and subsets S 1 , . . . , S m ⊆ U such that indices I ⊆ {1, . . . , m}, with | I | minimal, such that [ S i = U. i∈ I Approximation Algorithm: while U is not empty do 2 Pick the largest subset S i 3 Remove all elements of S i from U and from the other subsets 4 return a list of the sets we chose 1 Lec 18 – pg. 3 of 6 Sm i =1 S i = U, find The running time for a good implementation of this algorithm is à ! m ¯ ¯ X ¯S i ¯ O i =1 (see Exercise 35.3-3 of CLRS). Claim. The above algorithm gives a (ln |U | + 1)-approximation. Proof. Assume the optimal cover has size k. Let U i denote the value of U (our universe set) after i iterations of the loop. Clearly, for all i, the set U i can be covered by k sets. So one of these k sets | | | | must contain at least Uki elements, and therefore the set chosen on line 2 has size at least Uki . Thus, we have ¯ ¯ ¡ ¢¯ ¯ ¯U i+1 ¯ ≤ 1 − 1 ¯U i ¯ k for all i. This implies that ¯ ¯ ¡ ¢ ¯ ¯ ¯U i ¯ ≤ 1 − 1 i ¯U0 ¯ k for all i. Since 1 − 1k ≤ e−1/k , it follows that ¯ ¯ ¯ ¯ ¯U i ¯ ≤ e− i/k ¯U0 ¯ . In particular, letting n = |U0 |, we have ¯ ¯ ¯Uk(ln n+1) ¯ < 1 ¯ ¯ ¯Uk(ln n+1) ¯ = 0. =⇒ Thus, the loop exits after at most k(ln n + 1) iterations. 18.3 Partition NP-hard problem (Partition). Given a sorted list of numbers s 1 ≥ s 2 ≥ · · · ≥ s n , partition the indices {1, . . . , n} into two sets {1, . . . , n} = A t B such that the “cost” ( ) X X max si, si i ∈B i∈ A is minimized. Example. For the partition 12 10 9 7 4 3 2 it is optimal to take A = {1, 2, 7} and B = {3, 4, 5, 6}, so that X i∈ A s i = 24 and X s i = 23. i ∈B Lec 18 – pg. 4 of 6 Approximation Algorithm: 1 2 3 4 5 6 7 8 9 10 11 B ² is a parameter: for a given ², the running time is polynomial in n when we view ² as a constant m ← b1/²c By brute force, find an optimal partition {1, . . . , m} = A 0 t B0 for s 1 , . . . , s m A ← A0 B ← B0 for i ← m + 1 to n do P P if j∈ A s j ≤ j∈B s j then A ← A ∪ { i} else B ← B ∪ { i} return 〈 A, B〉 Note that this algorithm always returns a partition. The running time of a reasonable implementation is5 ¢ ¡ Θ 2m + n = Θ(n). Claim. The above algorithm gives a (1 + ²)-approximation. Proof. Without loss of generality,6 assume X si ≥ X si. i ∈B 0 i∈ A 0 Let H= n 1X si. 2 i=1 Notice that solving the partition problem amounts to finding a set A ⊆ {1, . . . , n} such that P P as close to H as possible. Moreover, since i∈ A s i + i∈B s i = 2H, we have ( ) X X D max si, si = H + , 2 i ∈B i∈ A where P i∈ A s i is ¯ ¯ ¯X X ¯¯ ¯ D=¯ s − s ¯. ¯ i ∈ A i i ∈B i ¯ • Case 1: X s i > H. i∈ A 0 P P In that case, the condition on line 7 is always false, seeing as i∈ A 0 s i > i∉ A 0 s i . So A = A 0 and B = {1, . . . , n} \ A 0 . In fact, approximation aside, I claim that this must be the optimal P P partition. To see this, first note that i∈B s i < H < i∈ A 0 s i . If there were a better partition 5 Of course, the dependence on ² is horrible. In a practical context, we would have to choose ² small enough to get a useful approximation but big enough that our algorithm finishes in a reasonable amount of time. This would be helped if we replaced line 3 with a more efficient subroutine. 6 We can have our algorithm check whether this equation holds, and switch the roles of A 0 and B0 if it doesn’t. Lec 18 – pg. 5 of 6 {1, . . . , n} = A ∗ t B∗ , then taking A 00 = A ∗ ∩{1, . . . , m} and B00 = B ∩{1, . . . , m} would give a partition of {1, . . . , m} in which ( ) X X X max si, si < si, i ∈B00 i ∈ A 00 i∈ A 0 contradicting the brute-force solution on line 3. • Case 2: X s i ≤ H. i∈ A 0 Note that, if A ever gets enlarged (i.e., if the condition on line 7 is ever true), then we have P D ≤ s i (where i is as in line 6). And if A is never enlarged, then it must be the case that i∈B s i P never exceeded i∈ A s i until the very last iteration of lines 6–10, in which s n is added to B. In that case we have D ≤ s n (why?). Either way, we must have D ≤ s m+1 and consequently ( max ) X i∈ A si, X si H+ = i ∈B D 2 ≤ H + 21 s m+1 . Thus, cost of the algorithm’s output cost of the algorithm’s output ≤ optimal cost H ≤ H + 12 s m+1 = 1+ = 1+ H 1 2 s m+1 H 1 2 s m+1 P 1 m+1 2 i =1 s i s m+1 = 1 + Pm+1 i =1 s i ≤ 1+ s m+1 (m + 1) s m+1 = 1+ 1 m+1 < 1 + ². Lec 18 – pg. 6 of 6