## 9.5 Handling NP-Hard Problems In the absence of polynomial-time algorithms for problems known to be *NP*-hard, what can we do about solving such problems? We presented one way in [Chapters 5](LiB0039.html#471) and [6](LiB0047.html#565). The backtracking and branch-and-bound algorithms for these problems are all worst-case nonpolynomial-time. However, they are often efficient for many large instances. Therefore, for a particular large instance of interest, a backtracking or branch-and-bound algorithm may suffice. Recall from [Section 5.3](LiB0072.html#840) that the Monte Carlo technique can be used to estimate whether a given algorithm would be efficient for a particular instance. If the estimate shows that it probably would be, we can try using the algorithm to solve that instance. Another approach is to find an algorithm that is efficient for a subclass of instances of an *NP*-hard problem. For example, the problem of probabilistic inference in a Bayesian network, discussed in [Section 6.3](LiB0050.html#606), is *NP*-hard. In general, a *Bayesian network* consists of a directed acyclic graph and a probability distribution. Polynomial-time algorithms have been found for the subclass of instances in which the graph is singly connected. A directed, acyclic graph is ***singly connected*** if there is no more than one path from any vertex to any other vertex. Pearl (1988) and Neapolitan (1990, 2003) discuss these algorithms. A third approach, investigated here, is to develop approximation algorithms. An ***approximation algorithm*** for an *NP*-hard optimization problem is an algorithm that is not guaranteed to give optimal solutions, but rather yields solutions that are reasonably close to optimal. Often we can obtain a bound that gives a guarantee as to bow close a solution is to being optimal. For example, we derive an approximation algorithm that gives a solution, which we will call *minapprox*, to a variant of the Traveling Salesperson Optimization problem. We show that  where *mindist* is the optimal solution. This does not mean that *minapprox* is always almost twice mindist. For many instances, it may be much closer or even equal to *mindist.* Rather, this means that we are guaranteed that *minapprox* will never be as great as twice *mindist.* We develop this algorithm and an improvement on it next. Then we further illustrate approximation algorithms by deriving one for another problem. ### 9.5.1 An Approximation Algorithm for the Traveling Salesperson Problem Our algorithm will be for the following variant of the problem. Example 9.18 Traveling Salesperson Problem with Triangular Inequality****Let a weighted, undirected graph *G* = (*V*, *E*) be given such that 1. There is an edge connecting every two distinct vertices. 2. If *W* (*u*, *v*) denotes the weight on the edge connecting vertex *u* to vertex *v*, then, for every other vertex *y*,  The second condition, called the ***triangular inequality***, is depicted in [Figure 9.10](#ch09fig10). It is satisfied if the weights represent actual distances ("as the crow flies") between cities. Recall that weight and distance terminology are used interchangeably for weighted graphs. The first condition implies that there is a two-way road connecting every city to every other city. The problem is to find the shortest path (optimal tour) starting and ending at the same vertex and visiting each other vertex exactly once. It can be shown that this variant of the problem is also *NP*-hard. **** [](fig9-10_0.jpg) Figure 9.10: The triangular inequality implies that the "distance" from *u* to *v* is no greater than the "distance" from is to *y* plus the "distance" from *y* to *v.* Notice that the graph in this variant of the problem is undirected. If we remove any edge from an optimal tour for such a graph, we have a spanning tree for the graph. Therefore, the total weight of a minimum spanning tree mustbe less than the total weight of an optimal tour. We can use Algorithm 4.1 or 4.2 to obtain a minimum spanning tree in polynomial time. By going twice around the spanning tree, we can convert it to a path that visits every city. This is illustrated in [Figure 9.11](#ch09fig11). A graph is depicted in [Figure 9.11](#ch09fig11)(a), a minimum spanning tree for the graph in [Figure 9.11](#ch09fig11)(b), and the path obtained by going twice around the tree in [Figure 9.11](#ch09fig11)(c). As the figure shows, the resulting path may visit some vertices more than once. We can convert the path to one that does not do this by taking "shortcuts." That is, we traverse the path, starting at some arbitrary vertex, and visit each unvisited vertex in sequence. When there is more than one unvisited vertex adjacent to the current vertex in the tree, we simply visit the closest one. If the only vertices adjacent to the current vertex have already been visited, we bypass them by means of a shortcut to the next unvisited vertex. The triangular inequality guarantees that the shortcut will not lengthen the path. [Figure 9.11](#ch09fig11)(d) shows the tour obtained using this technique. In that figure, we started with the bottom vertex on the left. Notice that the tour obtained is not optimal. However, if we start with the top left vertex, we Obtain an optimal tour. [](fig9-11_0.jpg) Figure 9.11: Obtaining an approximation to an optimal tour from a minimum spanning tree The method just outlined can be summarized in the following steps: 1. Determine a minimum spanning tree. 2. Create a path that visits every city by going twice around the tree. 3. Create a path that does not visit any vertex twice (that is, a tour) by taking shortcuts. In general, the tour obtained using this method is not necessarily optimal regardless of the starting vertex. However, the following theorem gives us a guarantee as to how close the tour is to being optimal. Theorem 9.6****Let *mindlist* be the total weight of an optimal tour and *minapprox* be the total weight of the tour obtained using the method just described. Then ****  Proof: As we have already discussed, the total weight of a minimum spanning tree is less than *mindist.* Because the total weight of *minapprox* is no more than the total weight of two minimum spanning trees, the theorem follows. It is possible to create instances that show that *minapprox* can be made arbitrarily close to 2 x *mindist.* Therefore, in general, the bound obtained in [Theorem 9.6](#ch09ex24) is the best we can do. We can obtain an even better approximation algorithm for this problem as follows. First obtain a minimum spanning tree as done above. Then consider the set *V*’ of all vertices that touch an odd number of edges. It is not hard to show that there must be an even number of such vertices. Pair up the vertices in *V*’ so that each vertex is paired with precisely one other vertex. Such a creation of vertex pairs is called a ***matching*** for *V*’. Add the edge connecting each vertex pair to the spanning tree. Because each vertex then has an even number of edges touching it, the resultant path visits every city. Furthermore, the total number of edges in this path is no greater than (and often is less than) the total number that would he obtained by simply going twice around the tree. [Figure 9.12](#ch09fig12)(a) shows a minimum spanning tree, and [Figure 9.12](#ch09fig12)(b) shows the path obtained from that tree with one possible matching. [Figure 9.12](#ch09fig12)(c) shows a tour obtained after shortcuts are taken. [](fig9-12_0.jpg) Figure 9.12: A tour obtained using a matching A ***minimal weight matching*** for *V*’ is one such that the total weight of the edges obtained from the matching is minimal. Lawler (1976) shows how to obtain a minimal weight matching in polynomial time. We therefore can approximately solve the variant of the Traveling Salesperson problem given in [Example 9.17](LiB0077.html#953) in polynomial-time using the following steps: 1. Obtain a minimum spanning tree. 2. Obtain a minimal weight matching of the vertices in *V*’, where *V*’ is the set of vertices in the spanning tree that touch an odd number of edges. 3. Create a path that visits every vertex by adding the edges connecting matched vertices to the tree. 4. Obtain a path that does not visit any vertex twice (that is, a tour) by taking shortcuts. [Figure 9.11](#ch09fig11) illustrates these steps without showing any actual weights. The following theorem shows that this method gives a better bound than the first method presented in this section. Theorem 9.7****Let *mindist* be the total weight of an optimal tour and *minapprox2* be the total weight of the tour obtained using the method of minimal weight matching. Then  Proof: Let *V*’ be the set of all vertices that touch an odd number of edges. Convert an optimal tour to a path connecting only the vertices in *V*’ by bypassing vertices not in *V*’. By the triangular inequality, the total weight of this path can be no greater than *mindist.* Furthermore, this path provides us with two matchings for the vertices in *V*’, as follows. Choose an arbitrary vertex in *V* and match it with the vertex on one side of it in the path. Then continue to match adjacent vertices in pairs going in this same direction. This is onematch. Next match the initial vertex with the vertex on the other side of it in the path, and continue to match adjacent vertices going in the other direction. This is a second match. Because the edges in the two matches comprise all the edges in the path, the sum of the total weights of the two matches is equal to the weight of the path. Therefore, at least one of the matches has total weight no greater than half the weight of the path. Because the weight of this path is no greater than *mindist*, and because the weight of any matching is at least as great as the weight of a minimal weight matching, we have  where *minmatch* is the weight of a minimal weight matching. Recall that the weight of a minimum spanning tree is less than *mindist.* Because the edges obtained in Step 3 of the method of minimal weight matching consist of the edges in a spanning tree and the edges obtained from a minimal matching, the total weight of those edges is less than 1.5 × *mindist.* The theorem now follows, because the total weight of the edges in the final tour obtained in Step 4 is no greater than the weight of those obtained in Step 3. It is possible to create instances for which the approximation can be made arbitrarily close to 1.5 × *mindist.* Therefore, in general, there is no better bound for this algorithm than the one obtained in [Theorem 9.7](#ch09ex25). Recall that our salesperson Nancy was last trying to find an optimal tour for her 40-city sales territory using a branch-and-bound algorithm (Algorithm 6.3) for the Traveling Salesperson problem. Because that algorithm is worst-case nonpolynomial-time, it may take many years to solve her particular instance. If the distances between Nancy's cities satisfy the assumptions in the Traveling Salesperson with Triangular Inequality problem, she finally has an alternative that is sure to work. That is, she can use the method of minimal weight matching to obtain a good approximation to an optimal tour in polynomial time. **** ### 9.5.2 An Approximation Algorithm for the Bin-Packing Problem We introduce the following new problem. Example 9.19****Bin–Packing Problem Let *n* items with sizes  be given, and suppose we are to pack the items in a capacity of 1. The problem is to determine the minimum number is bins necessary to pack all the items. **** This problem has been shown to be *NP*-hard. A, very simple approximation algorithm for this problem is called "first fit." The ***first-fit*** strategy places anitem in the first bin in which it fits. If it does not fit in a bin, a new bin is started. Another good idea is to pack the items in nonincreasing order. Therefore, our strategy is called ***nonincreasing first fit***. It can be described by the following high-level algorithm: ``` sort the items in nonincreasing order; while (there are still unpacked items ){ get next item; while (the item is not packed and there are more started bins){ get next bin; if(the item fits in the bin) pack it in the bin } if (the item is not packed){ start a new bin; place the item in the new bin; } } ``` [Figure 9.13](#ch09fig13) shows a result of applying this algorithm. Notice that it consists of a greedy algorithm within a greedy algorithm. That is, we greedily grab items, and for each item we greedily grab bins. It is left as an exercise to write a detailed version of this algorithm and show that it is θ (*n*2). Notice that the solution in [Figure 9.12](#ch09fig12) is not optimal. We could fit the items in only three bins if we placed the size 0.5 item, the size 0.3 item, and one of the size 0.2 items in the second bin, and placed the two size 0.4 items and one of the size 0.2 items in the third bin. [](fig9-13_0.jpg) Figure 9.13: A result of applying nonicreasing fit. Next we obtain a bound for how close the approximate solution is to an optimal solution. The bound is obtained in [Theorem 9.8](#ch09ex29). The proof of that theorem requires the following two lemmas. Lemma 9.1****Let *opt* be the optimal number of bins for a given instance of the Bin-Packing problem. Any item that is placed by the nonincreasing first-fit strategy in an extra bin (that is, in a bin with index greater than *opt*) has size at most equal to 1/3. ****  Proof: Let *i* be the index of the first item placed in bin *opt* + 1. Because the items are sorted in nonincreasing order, it suffices to show that  Suppose by way of contradiction that *s**i*≥ 1/3. Then  which means that all those bins with indices no greater than *opt* contain at most two items each. If every one of those bins contained two items, in an optimal solution there, would have to be two of the first *i* – 1 items in every bin. But because their sizes are all greater than , there would be no room for *s**i* in one of the bins. Therefore, at least one bin with index no greater than *opt* contains only one item. If every bin with index no greater than *opt* contained only one item, no two of them could fit in a bin together and the *i* the item could not fit with any one of them (otherwise, our algorithm would have placed it with one of them). But then an optimal solution would require more than *opt* bins. Therefore, at least one bin with index no greater than *opt* contains two items. We show that there is some *j* such that 0 < *j* *opt* for which the first *j* bins contain one item each and the remaining *opt – j* bins contain two items each. If this were not the case, there would be bins *B**k* and *B**m* with *k* < *m* such that *B**k* contained two items and *B**m* contained one item. However, because the items are packed in nonincreasing order, the item packed in *B**m* would be no larger than the first item packed in *B**k*, and *s**i* would be no larger than the second item packed in *B**k*. Therefore, the sum of the sizes of the item in *B**m* and *s**i* would be no greater than the sum of the sizes of the two items in *B**k*, which means that *s**i* would fit in *B**m*. Therefore, the conjecture above (concerning *j*) must be true, and the bins appear as depicted in [Figure 9.14](#ch09fig14). [](fig9-14_0.jpg) Figure 9.14: if si ≥ 1/3, our algorithm would pack the bine like this. Let an optimal solution be given. In such a solution, the first *j* items are in *j* distinct bins, because if any of them could fit together in a bin, our method would have put them together. Furthermore, items  are in the remaining *opt – j* bins, because none of them can fit with the first *j* items. Because our algorithm places two of each of these items in *opt – j*bins, there must be 2 x (*opt – j*) of these items. Because we assumed that the size of each of these items is greater than 1/3, there cannot be three of them in any of one of the remaining *opt – j* bins, which means that there must be exactly two items in each of these bins. Because we assumed that the size of *s**i* is also greater than 1/3, it cannot fit in the *opt – j* bins containing two items each. Furthermore, it cannot fit in one of the bins containing one of the first *j* items, because if it could fit with one of those items our algorithm would have placed it with that item. Because we assumed that this is an~optimal solution, *s**i* must be in one of the bins, which means that we have a contradiction, and our lemma is proven. Lemma 9.2****Let *opt* be the optimal number of bins for an instance of the Bin-Packaging problem. The number of items placed by the nonincreasing first fit strategy in extra bins is at most *opt* – 1. **** Proof: Because all the objects fit in *opt* bins,  Suppose by way of contradiction that our approximation algorithm does put *opt* items into extra bins. Let *z*1, *z*2,…, *z**opt* be the sizes of those items, and, for 1 ≤ *i* ≤ *opt*, let *tot**i* be the total size that our algorithm puts in bin *B**i*. It must be true that  because otherwise the item of size *z**i* could have been put in *B**i*. We therefore have  which contradicts what we showed at the beginning of the proof. This contradiction proves the lemma. Theorem 9.8****Let *opt* be the optimal number of bins for an instance of the Bin-Packing problem, and let *approx* be the number of bins used by the nonincreasing first fit algorithm. Then  Proof: By Lemmas 9.1 and 9.2, the nonincreasing first-fit algorithm puts at most *opt* – 1 items, each of size at most , in extra bins. Therefore, the number of extra bins is at most  where *k* = 0, 1, or 2. Taking the largest possible value of *k*, we conclude that the number of extra bins is less than or equal to (*opt* + 1) /3, which means that  and therefore  This ratio is maximized if *opt* = 1. However, when *opt* = 1, our approximation algorithm uses only one bin and therefore is optimal. This means that we can take *opt* = 2 to maximize the ratio and conclude that  **** It is possible to create instances of arbitrarily large size for which the ratio is exactly 3/2. Therefore, in general, we cannot improve on the bound obtained in [Theorem 9.8](#ch09ex29). One way to gain further insight into the quality of an approximation algorithm is to run empirical tests comparing the solutions obtained from the approximation with the optimal solutions. Our approximation algorithm for the Bin-Packing problem has been extensively tested for large values of n. You may wonder how this is possible when we have no polynomial-time algorithm that guarantees an optimal solution, which means that we cannot determine an optimal solution for a large value of it in a tolerable amount of time. Indeed, if we bad such an algorithm we would not bother with an approximation algorithm in the first place. The answer to this paradox is that in the case of the Bin-Packing problem we do not need to actually compute optimal solutions to gain insight into the quality of the approximations. Instead, we can compute the amount of unused space (the empty space) in the bins used by the approximation algorithm. The number of extra bins used by that algorithm can be no more than the amount of unused space. This is so because we can rearrange the items in our approximate solution so that they are in an optimal number pf bins, leaving the extra bins empty. The amount of unused space in this optimal solution plus the total space in the extra bins is equal to the amount of unused space in our approximate solution. Therefore, because the total space in the extra bins equals the number of extra bins, the number of extra bins can be no greater than the amount of unused space in our approximate solution. In an empirical study in which the input size was 128,000 and the item sizes were uniformly distributed between 0 and 1, our approximation algorithm used on the average about 64,000 bins, and on the average had about 100 units of unused space. This means that on the average the number of extra bins is bounded by 100 in the instances in this study. [Theorem 9.8](#ch09ex29) implies, for an approximate solution of 64,000, that  which means *opt* ≥ 42,666, and that the number of extra bins is no greater than 21,334. We see that the empirical study indicates that on the average our algorithm performs much better than the upper bound. For any particular instance of interest, we can compute the amount of unused space in the solution produced by the approximation algorithm. In this way we can determine how well the algorithm performs for that instance. For more examples of approximation algorithms, you are again referred to Garey and Johnson (1979).