算法分析英文幾何approximation

1、Algorithms Design and Analysis:Approximation AlgorithmsProf. Dr. Jinxing XieDept. of Mathematical SciencesTsinghua University, Beijing 100084, China Voice:(86-10)62787812 Fax:(86-10)62785847 pleteness is a worst-case statement. If the hard cases are rare, heuristics might work well in practice. e.g.

2、 the Simplex algorithm for solving Linear Programs The general problem is plete, but we might be confronted with a subcase that is actually polynomially solvable. e.g. 2-CNF-SAT can be solved efficiently We must only solve small instances of the problem and then exponential running time can be toler

3、ated Constants matter. e.g. 3-CNF-SAT can naively be solved in time O(2n), but it can also be solved in time 1.23883m In practice it is often sufficient to find a “good” near-optimal solution, so we can try approximation algorithmsHow to deal with NPC problems?Approximation algorithmAn algorithm tha

4、t returns near-optimal solutions is called approximation algorithm.An algorithm for a problem has an approximation ratio (or factor) of (n) if for any input of size n, the cost C of the solution produced by the algorithm is within a factor of (n) of the cost C* of an optimal solution: max(C/C*, C*/C

5、) =1)And this algorithm is called a (n)-approximation algorithm.Note: We call an algorithm a heuristic if we cannot prove that it is fast or correct. (e.g. metaheuristics Genetic algorithm etc.)Approximation schemeAn approximation scheme for an optimization problem is an approximation algorithm that

6、 takes as input not only an instance of the problem, but also a value 0Such that for any fixed 0, the scheme is a (1+)-approximation algorithm.A polynomial time approximation scheme (PTAS) is an approximation scheme with running time polynomial in the size n of its input instance, for any fixed 0.A

7、fully polynomial time approximation scheme (FPTAS) is an approximation scheme with running time polynomial both in (1/) and the size n of its input instance.Minimum Vertex Cover problemA vertex cover of an undirected graph G=(V,E) is a subset V of vertices such that if (u,v) E, then u V or v V (or b

8、oth).Basic idea:As long as there are nodes, choose an arbitrary edge (u,v), add u and v to the vertex cover and remove all edges incident to u and vAPPROX-VERTEX-COVER is a polynomial time 2-approximation algorithmLet A be the set of edges chosen by the algorithm (in Line 4),Then |C|=2|A|An optimal

9、cover C* must include at least one end point of each edge in A, thus |C*| = |A|Therefore |C| =2|A| = 2|C*|(Note: A is actually a maximal matching of G)RemarksTSP with triangle inequalitytriangle inequality: (e.g. Euclidean distance c on graph G=(V,E) for all u, v, w in V, c(u,w) = c(u,v) + c(v,w)Bas

10、ic idea: weight of MST is a lower bound on the length of the optimal tour use MST to create a tour O(V2)APPROX-TSP-TOUR is a polynomial time 2-approximation algorithmLet H* be an optimal tour, Then c(T) = c(H*)Let W be the walk, it traverses every edge of T exactly twice,Thus c(W) = 2c(T)Unfortunate

11、ly, W is generally not a tour. However, deleting one of the two visits to a vertex will not increase the total cost due to the triangle-inequality property!Finally, c(H) = c(W) = 2c(T) =1, there is no polynomial time -approximation algorithm for general TSP.By contradiction. (WLOG, assume =1 is an i

12、nteger)Suppose A is a -approximation algorithm for general TSP Then we can use it to solve HAMILTONIAN CYCLE problem.Given G=(V,E), an instance of HAMILTONIAN CYCLE problem, Let G=(V,E) be the complete graph on VGeneral TSPIf G has a hamiltonian cycle H, then (G,c) has a tour of cost |V|.If G has no

13、 hamiltonian cycle, then any tour in (G,c) has a cost of at least (|V|+1) + (|V|-1) = |V|+|V| |V|Thus:If G has a hamiltonian cycle H, then using A to (G, c) will return a tour with cost of |V|.If G has no hamiltonian cycle, then using A to (G, c) will return a tour with cost at least |V|.So A can so

14、lve hamiltonian cycle problem!The set-covering problemIt is a generalization of vertex-covering problem, thus it is NP-hard (NPO: NP Optimization)A greedy approximation algorithmComplexityNumber of loops: at most min(|X|, |F|)In each loop: at most O(|X| |F|)Totally: O(|X| |F| min(|X|, |F|) polynomia

15、lHarmonic number and the Theorem The dth harmonic number is Hd=H(d)= (H0=H(0)=0) H3= 11/6 2 Note: When k is small, the algorithm is not too bad, e.g. H3= 11/6 2 Approx-SC is a polynomial-time (1+ln|X|)-approximation algorithm ProofLemmaRandomizationA randomized algorithm for a problem has an approxi

16、mation ratio of (n) if for any input of size n, the expected cost C of the solution produced by the algorithm is within a factor of (n) of the cost C* of an optimal solution: max(C/C*, C*/C) =1)And this algorithm is called a randomized (n)-approximation algorithm.Example - MAX-3-CNF satisfiability p

17、roblem:Similar to 3-CNF-SAT, but the goal is to find the assignment of the variables that maximizes the number of clauses evaluating to 1RandomizationTheorem:The randomized algorithm that independently sets each variable to 1 with probability and to 0 with probability is a randomized 8/7-approximati

18、on algorithm to MAX-3-CNFProof. Suppose there are totally m clauses.Prclause i is unsatisfied = 1/2*1/2*1/2=1/8Prclause i is satisfied = 1-1/8=7/8Thus the expected number of satisfied clauses = 7m/8 (=C)Optimal solution can at most satisfy all m clauses: C*=mThus C*/C =1 for all (u,v) in E, x(v) = 0

19、 or 1 for all v in V Lower bound: Relaxation to 0 = x(v) =1The algorithm Approximation ratio = 2 Let C* be the optimal cover, z* be the value of the optimal solution to the linear programming then z* = w(C*) C is obviously a vertex cover, andThus w(C) = 2w(C*)The subset-sum problem Optimization vers

20、ion: . The sum is as large as possible but = tTrimming a list Remove from a list the element “close enough” to another numberL=: a sorted list (from small to big) 01(m), m=|L|The algorithm 01Example S= , t=308 and =0.4L0=L1=L2= (before TRIM) L2= (after TRIM)L3=(before TRIM) L3=(after TRIM) L3= (remove “l(fā)arger” number)L4= (before TRIM) L4=(after TRIM) L4=(remove “l(fā)arger” number)z*=302 = 101+201Optimal: 307=104+102+101Actually within 2%Proof Denote Pi= Pi-1 (Pi-1+xi) , the optimal solution y* PnThen Li is an ordered subset of Pi , z* = y* We need to show y*/z*