算法高级教程3.1Approximationalgorithms.pptVIP

Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell Approximation Algorithm * Definition 3.1.1 An approximation algorithm A for an optimization problem Q is a polynomial time algorithm such that given an input instance I for Q it will output some s∈S(I) We will denote by A(I) the value f(s) of the solution obtained by A. We need some way of comparing approximation algorithms and analyzing the quality of solutions produced by them Moreover the measure of goodness of an approximation algorithm must somehow relate the optimal solution to the solution produced by the algorithm Such measures are referred to as performance guarantees and the exact choice of such a measure is not obvious. * Absolute Performance Guarantees Definition 3.1.2 An α-absolute approximation algorithm is a polynomial time approximation algorithm for Q such that for some constant α0, * For example The planar coloring problem Find the minimum number of colors needed to color a planar graph G = (V, E). Theorem3.1.1 The problem of deciding whether a planar graph is colorable is NP-complete It is also well known that any planar graph is colorable In fact the infamous Four Color Theorem for planar maps tells us that every planar graph is colorable. * Theorem 3.1.2 Any planar graph can be colored using at most four colors. Hence, if m is the number of colors needed, then m≤4. An absolute approximation algorithm: PlanarColor(V, E) 1 if V=? then m ← 0 2 else if E= ? then m ← 1 3 else if Bipartite(V, E) then m ← 2 4 else m← 4 5 return m * PlanarColor(V, E) is a 1-absolute approximation algorithm because: Its time complexity is O(|E| + |V|), i.e. polynomial in the size of the graph because Bipartite(V, E) can be written so as to check each edge at most twice. * Bipartite(V, E) 1 for i←1 to n do node(i) ← 0 2 ENQUEUE(Q, 1); node(1) ← 1 3 while Q ≠? do 4 i←DEQUEUE(Q)