算法分析与设计AlgoDALectureNotesW13章节.pptVIP

Last Section Approximation Algorithm 直观推断、贪婪。。。 相对误差、精确率、性能比、c近似算法； TSP的近似算法 Nearest-neighbor algorithm 欧几里德类型实例 Twice-around-the-tree algorithm Christofide Algorithm 对TSP的所有实例求解 Approximation Algorithm The Vertex Cover Problem; 边----点、边； |v| vs. 2 0/1 Integer Knapsack; Sahni,生成所有小于等于k个物品的子集, PAS FPAS; 近似度收敛到1的近似算法； RAε≤1+ε。 SUBSETSUM 存在伪多项式时间算法的NP难问题，尺度变换， FPAS 令 , ;Θ（kn2）; RAε≤1+1/k Relative Performance Bound vs. Difference Bound Relative Performance Bound vs. Difference Bound R(I)=A(I)/OPT(I) D(I)= A(I) -OPT(I) =K （minimization） Planar Graph Coloring 3 color ? NPC Relative Performance Bound vs. Difference Bound R(I)=A(I)/OPT(I) D(I)= A(I) -OPT(I) =K （minimization） Planar Graph Coloring An approximation Algo. with the tightest Difference Bound? D(I)= A(I)-OPT(I)=1 Relative Performance Bound vs. Difference Bound R(I)=A(I)/OPT(I) D(I)= A(I) -OPT(I) =K （minimization） Planar Graph Coloring D(I)= A(I) -OPT(I)=1 Integer Knapsack What a D(I) you can have? Difference Bound for Integer Knapsack 除非P=NP，不存在有差界的整数背包问题的多项式近似算法 证明： 假设存在有差界的整数背包问题的近似算法A，则对Integer Knapsack 的任一实例 I，有 OPT(I) - A(I) ≤K，K 为正整数。 针对I，构造实例I’，使得对于1 ≤ j ≤ n, 有 s’j=sj, v’j=(K+1)vj Difference Bound for Integer Knapsack 则：I 与 I’ 的解相同，且I’ 的A算法解值 A(I’)=(K+1)A(I) I’ 的最优解值 OPT(I’)=(K+1)OPT(I) 因：OPT(I’) - A(I’) ≤K (A算法差界) 有：OPT(I) - A(I) ≤ 即：A可求得最优解 而：已知Integer Knapsack 是NP-Hard问题 Randomized Algorithm 随机算法 Verification of Matrix Products Input: Three n ? n matrices, A, B and C. Question: Does A?B = C? Verification of Matrix Products Deterministic algorithms： Trivial Algorithms: O(n3) Strassen: O(n2.81) Best deterministic algorithm: O(n2.376) Verification of Matrix Products Freivalds Algorithm AB= C= Compute the sum of a random subset of the rows of both AB and C. If the sums are different, return false (AB?C). Otherwise, either return true or try again to improve confidence. Verification of Matrix Products The sum