退一步海阔天空精品

退一步海闊天空- 淺談近似演算法 呂學一 (中央研究院 資訊科學所) .tw/hil/ 2004/11/12 MCU2004/11/12 MCU 1 1 approximation algorithmsapproximation algorithms 全省走透透 2004/11/12 MCU2004/11/12 MCU 2 2 approximation algorithmsapproximation algorithms Traveling Salesman Problem nInput: A graph with edge lengths nOutput: A shortest tour visiting each node of the input graph exactly once. 2004/11/12 MCU2004/11/12 MCU 3 3 approximation algorithmsapproximation algorithms 2 Illustration 3 2 1 1 3 2 4 2 2004/11/12 MCU2004/11/12 MCU 4 4 approximation algorithmsapproximation algorithms How hard is this problem? The Traveling Salesman Problem is NP-hard. Bad NewsBad News 2004/11/12 MCU2004/11/12 MCU 5 5 approximation algorithmsapproximation algorithms How hard is NP-hard? nSo far, scientist only knows how to solve such a problem on an n-node graph in O(cn) time for some constant c. 2004/11/12 MCU2004/11/12 MCU 6 6 approximation algorithmsapproximation algorithms That is, n“Impossible” to find an optimal solution for all graphs with only, say, 100 nodes. 2004/11/12 MCU2004/11/12 MCU 7 7 approximation algorithmsapproximation algorithms On the bright side nIf you can come up with an algorithm for such a problem that runs in O(n100000000000) time, then you will be awarded Turing Award for sure. 2004/11/12 MCU2004/11/12 MCU 8 8 approximation algorithmsapproximation algorithms CMI Millennium Prize nClay Mathematics Institute (Cambridge, MA, USA) offered US$100,000 for each of seven open problems on May 24, 2000 at Paris. | Birch and Swinnerton-Dyer Conjecture | Hodge Conjecture | Navier-Stokes Equations | P vs NP | Poincare Conjecture | Riemann Hypothesis | Yang-Mills Theory | 2004/11/12 MCU2004/11/12 MCU 9 9 approximation algorithmsapproximation algorithms NP-completeness = Dead end ? 2004/11/12 MCU2004/11/12 MCU1010approximation algorithmsapproximation algorithms 退一步 海闊天空 Approximation Algorithms (近似演算法) 2004/11/12 MCU2004/11/12 MCU1111approximation algorithmsapproximation algorithms Traveling Salesman Problem nInput: A graph with edge lengths nOutput: A near shortest tour visiting each node of the input graph exactly once. 2004/11/12 MCU2004/11/12 MCU1212approximation algorithmsapproximation algorithms 近似演算法的哲學 放下對完美的堅持, 往往就可以找到新的出路。 知所進退, 則近道矣! 2004/11/12 MCU2004/11/12 MCU1313approximation algorithmsapproximation algorithms 安徽省 桐城 西後街百子堂 2004/11/12 MCU2004/11/12 MCU1414approximation algorithmsapproximation algorithms 【桐城縣誌略】 康熙大學士兼禮部尚書張英 一紙書來只為牆， 讓他三尺又何妨。 長城萬里今猶在， 不見當年秦始皇。 2004/11/12 MCU2004/11/12 MCU1515approximation algorithmsapproximation algorithms 近似演算法的哲學 放下對完美的堅持, 往往就可以找到新的出路。 知所進退, 則近道矣! 2004/11/12 MCU2004/11/12 MCU1616approximation algorithmsapproximation algorithms Example 1 路燈問題 (Vertex Cover) 2004/11/12 MCU2004/11/12 MCU1717approximation algorithmsapproximation algorithms Vertex Cover Problem nInput: A graph G nOutput: A smallest vertex subset of G that covers all edges of G. 2004/11/12 MCU2004/11/12 MCU1818approximation algorithmsapproximation algorithms Illustration 2004/11/12 MCU2004/11/12 MCU1919approximation algorithmsapproximation algorithms The Vertex Cover Problem is also NP-hard 2004/11/12 MCU2004/11/12 MCU2020approximation algorithmsapproximation algorithms Vertex Cover Problem nInput: A graph G nOutput: A near smallest vertex subset of G that covers all edges of G. 2004/11/12 MCU2004/11/12 MCU2121approximation algorithmsapproximation algorithms An approximation algorithm for the vertex cover problem nInitially, let S be an empty set. nRepeat until G has no edges: Arbitrarily choose an edge (u, v) of G. Insert u and v into S. Delete all edges of G incident to u or v. nOutput S. 2004/11/12 MCU2004/11/12 MCU2222approximation algorithmsapproximation algorithms Illustration 2004/11/12 MCU2004/11/12 MCU2323approximation algorithmsapproximation algorithms Three questions nQ1: Is the output vertex set indeed a vertex cover of the input graph? nQ2: Does the algorithm run in polynomial time? nQ3: Is the quality of the output solution close to optimal? 2004/11/12 MCU2004/11/12 MCU2424approximation algorithmsapproximation algorithms Q1: feasibility? nYes. 2004/11/12 MCU2004/11/12 MCU2525approximation algorithmsapproximation algorithms Q2: tractability? nIt is not difficult to see that this algorithm runs in linear time. O(n + m) time, where n is the number of vertices and m is the number of edges in G. 2004/11/12 MCU2004/11/12 MCU2626approximation algorithmsapproximation algorithms Q3: Quality? nThe output vertex cover has size at most 2 times that of any optimal vertex cover. 2004/11/12 MCU2004/11/12 MCU2727approximation algorithmsapproximation algorithms Such an algorithm is called a 2-approximation for vertex cover problem 2004/11/12 MCU2004/11/12 MCU2828approximation algorithmsapproximation algorithms Approximation Algorithm nCriterion 1: feasibility Always output a feasible solution. nCriterion 2: tractability Always runs in polynomial time. nCriterion 3: quality The solutions quality is always provably not too far from that of an optimal solution. 2004/11/12 MCU2004/11/12 MCU2929approximation algorithmsapproximation algorithms Can one do better than 2-approximation for Vertex Cover? 2004/11/12 MCU2004/11/12 MCU3030approximation algorithmsapproximation algorithms Surprise! nThat 2-approximation was known for 30 years. nIt remains the best known approximation algorithm for the vertex cover problem! nFinding a 1.166-approximation is known to be NP-hard. nEven a 1.9-approximation would be a significant breakthrough. n向公園路燈管理局致敬 2004/11/12 MCU2004/11/12 MCU3131approximation algorithmsapproximation algorithms Example 2 全省走透透 (traveling salesman) 2004/11/12 MCU2004/11/12 MCU3232approximation algorithmsapproximation algorithms Traveling Salesman Problem nInput: A graph with edge lengths nOutput: A near shortest tour visiting each node of the input graph exactly once. 2004/11/12 MCU2004/11/12 MCU3333approximation algorithmsapproximation algorithms What a hard problem! nWe already mentioned that this problem is NP-hard. nMoreover, finding f(n)-approximation for this problem with respect to any function f(n) remains NP-hard! 2004/11/12 MCU2004/11/12 MCU3434approximation algorithmsapproximation algorithms Dead end? 2004/11/12 MCU2004/11/12 MCU3535approximation algorithmsapproximation algorithms 山不轉 路轉! 替問題加上合理的限制: Metric Traveling Salesman Problem. 2004/11/12 MCU2004/11/12 MCU3636approximation algorithmsapproximation algorithms Metric Traveling Salesman nInput: A complete graph with edge lengths that satisfies triangle inequality nOutput: A near shortest tour visiting each node of the input graph exactly once. 2004/11/12 MCU2004/11/12 MCU3737approximation algorithmsapproximation algorithms 三角不等式 n兩邊和大於或等於 第三邊: ndist(u, v) + dist(v, w) dist(u, w) 2 3 2 1 1 3 2 4 2 2004/11/12 MCU2004/11/12 MCU3838approximation algorithmsapproximation algorithms A 2-approximation nStep 1: finding a minimum spanning tree T of G. nStep 2: short-cutting a depth-first traversal of T into a tour of G. 2 3 2 1 1 3 2 4 2 2004/11/12 MCU2004/11/12 MCU3939approximation algorithmsapproximation algorithms Q1: feasibility nThe input graph G is a complete graph, so any tour of G is a feasible solution. 2004/11/12 MCU2004/11/12 MCU4040approximation algorithmsapproximation algorithms Q2: tractability nMinimum spanning tree can be found in polynomial time. nShort-cutting is easy. 2004/11/12 MCU2004/11/12 MCU4141approximation algorithmsapproximation algorithms Q3: quality nThis is a 2-approximation. The optimal tour is a spanning tree plus an edge. So, length(T) length(optimal tour). length(shortcut tour) 2*length(T). 2004/11/12 MCU2004/11/12 MCU4242approximation algorithmsapproximation algorithms Christofides improvement invented in 1976 2004/11/12 MCU2004/11/12 MCU4343approximation algorithmsapproximation algorithms A 1.5-approximation nStep 1: finding a minimum spanning tree T of G. nStep 2: find a minimum matching M among the nodes with odd degrees in T. nStep 3: short-cutting an Euler tour of TM into a tour of G. 2 3 2 1 1 3 2 4 2 2004/11/12 MCU2004/11/12 MCU4444approximation algorithmsapproximation algorithms Best known result nChristofides 1.5- approximation remains the best known result for metric traveling salesman problem. 2004/11/12 MCU2004/11/12 MCU4545approximation algorithmsapproximation algorithms Euclidean Traveling Salesman nInput: A graph specified by points in an Euclidean space. nOutput: A near shortest tour visiting each node of the input graph exactly once. 2004/11/12 MCU2004/11/12 MCU4646approximation algorithmsapproximation algorithms Approximation Scheme nSanjeev Arora, IEEE FOCS 1996. 2004/11/12 MCU2004/11/12 MCU4747approximation algorithmsapproximation algorithms Example 3 掃黑的藝術 (maximum cut) 2004/11/12 MCU2004/11/12 MCU4848approximation algorithmsapproximation algorithms Maximum Cut Problem nInput: A graph G nOutput: A partition of Gs nodes into A and B that maximizes the number of edges between A and B. 2004/11/12 MCU2004/11/12 MCU4949approximation algorithmsapproximation algorithms Illustration 2004/11/12 MCU2004/11/12 MCU5050approximation algorithmsapproximation algorithms A randomized approximation nRepeat the following randomized subroutine for, say, 100 times, and then output the best cut among them. For each node v of G, n put v into A with probability . 2004/11/12 MCU2004/11/12 MCU5151approximation algorithmsapproximation algorithms Q1: feasibility nAny partition is a feasible solution. 2004/11/12 MCU2004/11/12 MCU5252approximation algorithmsapproximation algorithms Q2: tractability nThrowing a fair coin is “easy” to simulate by computers. As a matter of fact, the existence of pseudo- random generator implies NPP. 2004/11/12 MCU2004/11/12 MCU5353approximation algorithmsapproximation algorithms Q3: quality? nOne can prove that this simple algorithm is a 2-approximation with very high probability (something like 1-1/2100). 2004/11/12 MCU2004/11/12 MCU5454approximation algorithmsapproximation algorithms Can one do better than 2- approximation? nFor about 20 years, the above 2- approximation was the best known result for maximum cut. 2004/11/12 MCU2004/11/12 MCU5555approximation algorithmsapproximation algorithms Semidefinite Approximation Goemans and Williamson, ACM STOC 1994 2004/11/12 MCU2004/11/12 MCU5656approximation algorithmsapproximation algorithms A seminal paper n1/0.878-approximation for MAXCUT nInitiate a series of research in Operations Research, Scientific Computing, and Approximation Algorithms. 2004/11/12 MCU2004/11/12 MCU5757approximation algorithmsapproximation algorithms Traditional approach Integer Linear Program Integral solution Linear Program Fractional solution relaxation Rounding ApproximationSolver 2004/11/12 MCU2004/11/12 MCU5858approximation algorithmsapproximation algorithms SDP-based approach Quadratic Program Scalar solution Semi-definite Program Vector solution relaxation Rounding ApproximationSolver 2004/11/12 MCU2004/11/12 MCU5959approximation algorithmsapproximation algorithms Conclusion n勇於嘗試, 努力創新 n一篇好作品的影響, 往往遠甚於許多普 通的論文. (跳高) n.tw/hil/wput/approx-mcu- 2004.ppt 2004/11/12 MCU2004/11/12 MCU6060approximation algorithmsapproximation algorithms !Kue-RBl5YIsb*Pzi2WGp9%Mwg0TDn7#Kud)RBk4YIrb*Oyi2VFp9$Mwf+TDm6#Ktd)QAk4XHrb&Oyh1VFo8$Mvf+SCm6ZJtc(QAj3XHqa&Nxh1UEo8!Lve-SCl5ZJsc(Pzj3WGqa%Nxg0UEn7!Lue-RBl5YIsc*Pzi2WGp9%Nwg0TDn7#Kue)RBk4YIrb*Pyi2VFp9$Mwg+TDm6#Ktd)QAk4XHrb&Oyh1VFo8$Mvf+SCm6ZJtd(QAj3XHqa&Oxh1UEo8!Lvf-SCl5ZJsc(Qzj3WGqa%Nxh0UEn7!Lue1VEo8$Lvf+SCm5ZJtc(QAj3XGqa&Nxh1UEo7!Lve-SCl5ZIsc(Pzj3WGq9%Nxg0UDn7!Kue- RBl4YIsb*Pzi2WFp9%Mwg0TDn6#Kud)RBk4YHrb*Oyi2VFp8$Mwf+TDm6#Jtd)QAk4XHra&Oyh1VFo8$Lvf+SCm6ZJtc(QAj3XGqa&Nxh1UEo7!Lve-SCl5ZIsc(Pzj3WGq9%Nxg0UEn7!Kue-RBl5YIsb*Pzi2WGp9%Mwg0TDn7#Kud)RBk4YIrb*Oyi2VFp9$Mwf+TDm6#Ktd)QAk4XHra&Oyh1VFo8$Lvf+SCm6ZJtc(QAj3XHqa&Nxh1UEo8!Lve-SCl5ZJsc(Pzj3WGqa%Nxg0UEn7!Lue- RBl5YIsc*Pzi2WGp9%Nwg0TDn7#Kud)RBk4YIrb*Oyi2VFp9$Mwf+TDm6#Ktd)QAk4XHrb&Oyh1VFo8*Pyi2WFp9%Mwg+TDn6#Kud)RAk4YHrb*Oyi1VFp8$Mwf+TCm6#Jtd)QAk3XHra&Oyh1VEo8$Lvf+SCm5ZJtc(QAj3XGqa&Nxh0UEo7!Lve-SBl5ZIsc(Pzj2WGq9%Nxg0UDn7!Kue-RBl4YIsb*Pzi2WFp9%Mwg0TDn6#Kud)RBk4YHrb*Oyi2VFp8$Mwf+TDm6#Jtd)QAk4XHra&Oyh1VEo8$Lvf+SCm5ZJtc(QAj3XGqa&Nxh1UEo7!Lve-SCl5ZIsc(Pzj3WGq9%Nxg0UEn7!Kue- RBl5YIsb*Pzi2WGp9%Mwg0TDn7#Kud)RBk4YHrb*Oyi2VFp8$Mwf+TDm6#Jtd)QAk4XHra&Oyh1VFo8$Lvf+SCm6ZJtc(QAj3XHqa&Nxh1UEo8!Lve-SCl5ZJsc(Pzj3WGqa%Nxg0UEn7!Lue-RBl5YIsb*Pzi2WGp9%Mwg0TDn7#Kud)REo7!Lve-SBl5ZIsc*Pzj2WGq9%Nwg0UDn7!Kue)RBl4YIsb*Pyi2WFp9%Mwg+TDn6#Kud)RAk4YHrb*Oyi1VFp8$Mwf+TCm6#Jtd)QAk3XHra&Oyh1VEo8$Lvf-SCm5ZJtc(Qzj3XGqa&Nxh0UEo7!Lve-SBl5ZIsc(Pzj2WGq9%Nxg0UDn7!Kue- RBl4YIsb*Pzi2WFp9%Mwg0TDn6#Kud)RBk4YHrb*Oyi1VFp8$Mwf+TCm6#Jtd)QAk3XHra&Oyh1VEo8$Lvf+SCm5ZJtc(QAj3XGqa&Nxh1UEo7!Lve-SCl5ZIsc(Pzj3WGq9%Nxg0UEn7!Kue-RBl5YIsb*Pzi2WFpc(Qzj3XGqa%Nxh0UEo7!Lue-SBl5ZIsc*Pzj2WGp9%Nwg0UDn7#Kue)RBl4YIrb*Pyi2WFp9$Mwg+TDn6#Ktd)RAk4YHrb&Oyi1VFp8$Mvf+TCm6#Jtd(QAk3XHra&Oxh1VEo8$Lvf-SCm5ZJsc(Qzj3XGqa%Nxh0UEo7!Lue- SBl5ZIsc*Pzj2WGq9%Nwg0UDn7!Kue)RBl4YIsb*Pyi2WFp9%Mwg+TDn6#Kud)RAk4YHrb*Oyi1VFp8$Mwf+TCm6#Jtd(QAk3XHra&Oxh1VEo8$Lvf-SCp9$Mwf+TDm6#Ktd)QAk4XHrb&Oyh1VFo8$Mvf+SCm6ZJtd(QAj3XHqa&Oxh1UEo8!Lvf-SCl5ZJsc(Qzj3WGqa%Nxh0UEn7!Lue-SBl5YIsc*Pzj2WGp9%Nwg0TDn7#Kue)RBk4YIrb*Pyi2VFp9$Mwg+TDm6#Ktd)RAk4XHrb&Oyi1VFo8$Mvf+TCm6ZJtd(QAk3XHqa&Oxh1VEo8!Lvf-SCm5ZJsc(Qzj3WGqa%Nxh0UEn7!Lue-SBo8$Lvf+SCm6ZJtc(QAj3XGqa&Nxh1UEo7!Lve- SCl5ZIsc(Pzj3WGq9%Nxg0UEn7!Kue-RBl5YIsb*Pzi2WGp9%Mwg0TDn7#Kud)RBk4YIrb*Oyi2VFp9$Mwf+TDm6#Ktd)QAk4XHra&Oyh1VFo8$Lvf+SCm6ZJtc(QAj3XHqa&Nxh1UEo8!Lve-SCl5ZJsc(Pzj3WGqa%Nxg0UEn7!Lue-RBl5YIsf-SCm5ZJtc(Qzj3XGqa&Nxh0UEo7!Lve-SBl5ZIsc(Pzj2WGq9%Nxg0UDn7!Kue)RBl4YIsb*Pyi2WFp9%Mwg+TDn6#Kud)RAk4YHrb*Oyi1VFp8$Mwf+TCm6#Jtd)QAk3XHra&Oyh1VEo8$Lvf+SCm5ZJtc(QAj3XGqa&Nxh0UEo7!Lve-SBl5ZIsc(Pzj2WGq9%Nxg0UDn7!Kue- RBl4YIsb*Pzi2WFp9%Mwg0TDn6#Kxh0UEn7!Lue-SBl5YIsc*Pzj2WGp9%Nwg0UDn7#Kue)RBl4YIrb*Pyi2WFp9$Mwg+TDn6#Ktd)RAk4YHrb&Oyi1VFo8$Mvf+TCm6ZJtd(QAk3XHqa&Oxh1VEo8!Lvf-SCm5ZJsc(Qzj3XGqa%Nxh0UEo7!Lue-SBl5ZIsc*Pzj2WGq9%Nwg0UDn7!Kue)RBl4YIrb*Pyi2WFp9$Mwg+TDn6#Ktd)RAk4!Lue-RBl5YIsb*Pzi2WGp9%Mwg0TDn7#Kud)RBk4YIrb*Oyi2VFp9$Mwf+TDm6#Ktd)QAk4XHrb&Oyh1VFo8$Mvf+SCm6ZJtd(QAj3XHqa&Oxh1UEo8!Lve-SCl5ZJsc(Pzj3WGqa%Nxg0UEn7!Lue- RBl5YIsc*Pzi2WGp9%Nwg0TGqa&Nxh0UEo7!Lve-SBl5ZIsc(Pzj2WGq9%Nxg0UDn7!Kue-RBl4YIsb*Pzi2WFp9%Mwg0TDn6#Kud)RBk4YHrb*Oyi2VFp8$Mwf+TCm6#Jtd)QAk3XHra&Oyh1VEo8$Lvf+SCm5ZJtc(QAj3XGqa&Nxh1UEo7!Lve-SCl5ZIsc(Pzj3WGq9%Nxg0UEn7&Oxh1VEo8!Lvf-SCm5ZJsc(Qzj3XGqa%Nxh0UEo7!Lue-SBl5ZIsc*Pzj2WGp9%Nwg0UDn7#Kue)RBl4YIrb*Pyi2WFp9$Mwg+TDn6#Ktd)RAk4YHrb&Oyi1VFp8$Mvf+TCm6#Jtd(QAk3XHra&Oxh1VEo8$Lvf-SCm5ZJtc(Qzj3XGqa%Nxh0UEo7!Lue- SFo8$Mvf+SCm6ZJtd(QAj3XHqa&Nxh1UEo8!Lve-SCl5ZJsc(Pzj3WGqa%Nxg0UEn7!Lue-RBl5YIsc*Pzi2WGp9%Nwg0TDn7#Kue)RBk4YIrb*Pyi2VFp9$Mwg+TDm6#Ktd)QAk