版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
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*
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 彎管機plc課程設計
- 商鋪聯(lián)營合同
- 小班活躍氣氛課程設計
- 作業(yè)調(diào)度實驗課程設計
- 幼兒趣味性街舞課程設計
- 我的爸爸主題課程設計
- 運動健身行業(yè)健身指導與課程設計方案
- 車站建筑采購合同范文
- 車牌號抵押合同范文
- 家具家電采購合同
- 2024年商鋪租賃終止合同范本(四篇)
- 康養(yǎng)運營方案
- 安保行業(yè)培訓合同
- TSG 23-2021 氣瓶安全技術規(guī)程 含2024年第1號修改單
- 2024-2030年聚甲基丙烯酸甲酯(PMMA)行業(yè)市場現(xiàn)狀供需分析及投資評估規(guī)劃分析研究報告
- 河南省安陽市龍安區(qū)2023-2024學年五年級上學期期末英語試題
- 彈性力學仿真軟件:Altair HyperWorks:HyperStudy設計研究與優(yōu)化教程
- 教科版小學科學六年級上冊期末考試試卷(含答案)
- 北京課改版小學英語五年級上冊-知識清單
- 通訊員培訓講課
- “勞動、人事、工資”三項制度改革
評論
0/150
提交評論