1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 72

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 72)

SO, if the graphs we are interested in happen to be trees, the factthat NODE COVER and INDEPENDENT SET are NP-complete is irrelevant. Manyother NP-complete problems on graphs are solved by similar algorithms whenspecialized to trees, see for example Problem 7.4.1.0Approximation Algorithms,When facing an NP-complete optimization problem, we may want to consideralgorithms that do not produce optimum solutions, but solutions guaranteed tob~ close to the optimum. Suppose that we wish to obtain such solutions foran optimization problem, maximization or minimization. For each instance xof this problem, there is an optimum solution with value opt(x); let us assumethat opt (x) is always a positive integer (this is the case with all optimizationproblems we study here; we can easily spot and solve instances in which opt iszero).Suppose now that we have a polynomial algorithm A which, when presentedwith instance x of the optimization problem, returns some solution with valueA(x).

Since the problem is NP-complete and A is polynomial, we cannot realistically hope that A(x) is always the optimum value. But suppose that we knowthat the following inequality always ~olds:lopt(x) - A(x)1opt(x)where E is some positive real number, hopefully very small, that bounds fromabove the worst-case relative error of algorithm A. (The absolute value in this inequality allows us to treat both minimization and maximization problems withinthe same framework.) If algorithm A satisfies this inequality for all instances xof the problem, then it is called an E-approximation algorithm.Once an optimization problem has been shown to be NP-complete, the following question becomes most important: Are there E-approximation algorithmsfor this problem? And if so, how small can E be? Let us observe at the outsetthat such questions are meaningful only if we assume that P ::j:.

NP, because, ifP = NP, then the problem can be solved exactly, with E = O.All NP-complete optimization problems can therefore be subdivided intothree large categories:336Chapter 7: NP-COMPLETENESS(a) Problems that are fully approximable, in that there is an E-approximatepolynomial-time algorithm for them for all I' > 0, however small. Of theNP-complete optimization problems we have seen, only TWO-MACHINESCHEDULING (in which we wish to minimize t.he finishing time D) fallsinto this most fortunate category.(b) Problems that are partly approximable, in that there are E-approximatepolynomial-time algorithms for them for some range of E'S, but -unless ofcourse P = NP- this range dops not reach all the way down to zero, aswith the fully approximable problems.

Of the NP-complete optimizationproblems we have seen, NODE COVER and MAX SAT fall into t.his intermediate class.(c) Problems that are inapproximable, that is, there is no E-approximationalgorithm for them, with however large I' -unless of course P = NP. Ofthe NP-complete optimization problems we have seen in this chapter, unfortunately many fall into this cat.egory: the TRAVELING SALESMAN PROBLEM, CLIQUE, INDEPENDENT SET, as well as the problem of minimizing thenumber of states of a detPrministic automaton equivalent to a given regular expression in output polynomial time (recall the corollary to Theorem7.3.8).Example 7.4.2: Let us describe a I-approximation algorithm for NODE COVER-·that is to say, an algorithm which, for any graph, returns a node cover that isat. most twice the optimum size.

The algorithm is very simple:C:=0while there is an edge [u, v] left in G doadd u and v to C, and delete them from GFor example, in the graph in Figure 7-13, the algorit.hm might start bychoosing edge [a, b] ane! inserting both endpoints in C; both nodes (and theiradjacent edges, of course) are then deleted from G. Next [e, fl might be chosen,and finally [g, h]. The resulting set C is a node cover, because each edge in Gmust touch one of its nodes (either because it was chosen by the algorithm, orbecause it was deleted by it). In the present example, C = {a,b,e,f,g,h}, hassix nodes, which is at most twice the optimum value -in this case, four.To prove the "at most twice" guarantee, consider the cover C returned bythe algorithm, and let 6 be the optimum node cover. ICI is exactly twice thenumber of edges chosen by the algorithm. However, t.hese edges by the very waythey were chosen, have no vertices in common, and for each of them at leastone of its endpoints must be in 6 -because 6 is a node cover.

It follows thatthe number of edges chosen by the algorithm is no larger than the optimum setcover, and hence ICI :S 2 '161, and this is indeed a I-approximation algorithm.7.4: Coping with NP-completeness337bao--------o--------oced~----~----~ft>"----¢hFigure 7-13Can we do better? Depressingly, this simple approximation algorithm is thebest one known for the NODE COVER problem.

And only very recently have webeen able to prove that, unless P = NP, there is no E-approximation algorithmfor NODE COVER for any E < ~.<>Example 7.4.3: However, for TWO-MACHINE SCHEDULING, there is no limit tohow close to the optimum we can get: For any E > 0 there is an E-approximationalgorithm for this problem.This family of algorithms is based on an idea that we have already seen:Recall that the PARTITION problem can be solved in time O(nS) (where n is thenumber of integers, and S is their sum; see Section 6.2). It is very easy to seethat this algorithm can be rather trivially adapted to solve the TWO-MACHINESCHEDULING (finding the smallest D): The B(i) sets are extended to includesums up to S (not just up to H = ~S).

The smallest sum in B(n) that is 2;. ~Sis the desired minimum D.One more idea is needed to arrive at our approximation algorithm: Consideran instance of TWO-MACHINE SCHEDULING with these task lengths45362,134537,85879,56390,145627,197342,83625,126789,38562,75402,with n = 10, and S:::::: 106 . Solving it by our exact O(nS) algorithm would costus an unappetizing 107 steps. But suppose instead that we round up the tasklengths to the next hundred.

We obtain the numbers45400,134600,85900,56400,145700,197400,83700,126800,38600,75500,which is really the same as454,1346,859,564,1457,1974,837,1268,386,755,Chapter 7: NP-COMPLETENESS338(normalizing by 100); thus we can now solve this instance in about 105 steps.By sacrificing a little in accuracy (the optimum of the new problem is clearlynot very far from the original one), we have decreased the time requirements ahundredfold!It is easy to prove that, if we round up to the next kth power of ten, thedifference between the two optimal values is no more than nlOk. To calculate therelative error, this quantity must be divided by the optimum, which, obviously,can be no less than ~.

We have thu~ a 2n1ok -approximation algorithm, whoserunning time is O( ~). By setting 2n1ok equal to any desirable f > 0, we arriveat an algorithm whose running time is O( ~2) -certainly a polynomial.<>Example 7.4.4: How does one prove that a problem is inapproximable (or notfully approximable)? For most optimization problems of interest, this questionhad been one of the most stubborn open problems, and required the developmentof novel ideas and mathematical techniques (see the references at the end of thischapter).

But let us look at a case in which such a proof is relatively easy, thatof the TRAVELING SALESMAN PROBLEM.Suppose that we are given some large number f, and we must prove that,unless P = Np, there is no f-approximation algorithm for the TRAVELINGSALESMAN PROBLEM. We know that the HAMILTON CYCLE problem is NPcomplete; we shall show that, if there is an f-approximation algorithm for theTRAVELING SALESMAN PROBLEM, then there is a polynomial-time algorithmfor the HAMILTON CYCLE problem.

Let us start with any instance G of theHAMILTON CYCLE problem, with n nodes. We apply to it the simple reductionfrom HAMILTON CYCLE to TRAVELING SALESMAN PROBLEM (recall the proofof Theorem 7.3.4), but with a twist: The distances dij are now the following(compare with the proof of Theorem 7.3.4):0dij = { 12 + nfif i = j;if (Vi,Vj) E G;otherwise.The instance constructed has the following interesting property: If G has aHamilton cycle, then the optimum cost of a tour is n; if, however, there is noHamilton cycle, then the optimum cost is greater than n(l + f) -because atleast one distance 2 + nf must be traversed, in addition to at least n - 1 othersof cost at least 1.Suppose that we had a polynomial-time f-approximation algorithm A forthe TRAVELING SALESMAN PROBLEM.

Then we would be able to tell whether Ghas a Hamilton cycle as follows: Run algorithm A on the given instance of theTRAVELING SALESMAN PROBLEM. Then we have these two cases:7.4: Coping with NP-completeness339(a) If the solution returned has cost::::: n(l + €) + 1, then we know that theoptimum cannot be n, because in that case the relative error of A wouldhave been at leastIn(l + €) + 1 - nl-'---'-----'-------'> €,nwhich contradicts our hypothesis that A is an €-approximation algorithm.Since the optimum solution is larger than n, we conclude that G has noHamilton cycle.(b) If, however, the solution returned by A has cost:::; n(l + €), then we knowthat the optimum solution must be n. This is because our instance wasdesigned so that it cannot have a tour of cost between n + 1 and n(l + €).Hence, in this case G has a Hamilton cycle.It follows that, by applying the polynomial algorithm A on the instance ofthe TRAVELING SALESMAN PROBLEM that we constructed from G in polynomialtime, we can tell whether G has a Hamilton cycle --which implies that P = Np.Since this argument can be carried out for any € > 0, however large, we mustconclude that the TRAVELING SALESMAN PROBLEM is inapproximable.<>Ways of coping with NP-completeness often mix well: Once we realizethat the TRAVELING SALESMAN PROBLEM is inapproximable, we may want toapproximate special cases of the problem.

Характеристики

Список файлов решённой задачи