NPC问题与近似算法.pptx

定义：如果一个问题Y可以通过调用问题X且 通过poly-time的时间转化得到，我们称： yx,Examplel: Independent Set & Vertex Cover IS: If there is IS of G in size of =k,VC: If there is IS of G in size of =k, Observation: SUV is IS if and only if VS is VC of the graph G Conclusion： IS /,VC & VC,Example2: Vertex Cover p Set Cover SC: Given a set U of elements, a collection M of subset of U Sp S2eeeSn, and a integer k, ask if 3S o m, & | S | sZ.Us = U iuS,我们怎样证明h问题是NPC的呢？,定义： 如果问题X满足以下条件, 1. X eNP 2. 对于任意YeNP,Yp X,那么X属于NPCfeiRCurr-SAT) I (sat) Q-cnf-sat) (CUQUEJ (SUBSET-SUM； iVertex-cover),(kAM-CYCL 弓 (tsP-,证明： The Clique Problem is Np-complete CDShow that a given clique can be checked in poly-time Show that 3-CNF-SAT 勺 Clique,令为一个k子句的 3-CNF ,且C=l必I；,我们如何构建一幅图G(V,E)将图的团和3 CNF问题联系起来？,I J I I I,G = * V X2 V Xy,Fijurc 34.14 The graph G derived from the 3-CNF formula 0 = Ci A C2 A C3, where C = (xi v -X2 v 工3), C2 = (-xi V X2 v 心)，and C3 = (xi v X2 V X3), in reducing 3-CNF-SAT to CLIQUE. A satisfying assignment of the formula has x2 = 0, x3 = 1, and 勺 either 0 or 1. This as.signment satisfies Ci with -X2, and it satisfies C2 and C3 with JI3, corresponding to the clique with lightly shaded vertices.,对于每个子句G =；履济匚,我们在图中 添加3个结点咋，如果结点V/, V- J 满足以下两个条件，就连边： 1. iw j 2. /；尹iZy 4/,例1 ： Load Balancing Problem 问题描述： 1. 给定n个工作，工作j需要时间同 日寸拥有m台机器。

2. 定义机器i的奂载为：4 冲 3. 定义总奂载：T = m/x(,4.目标：最小化总奂载,近似算法 每次任意选择一个未安才非的工作，夺它安 排在当前奂载最小的机器上,这是一个2倍近似算法,证明： 1. OPT y t.&OPT max m j J J J 2. 假设Mj是奂载最大的机器，工作j是机器i最,后一个工作，我们有： 1 TLjJ Xj30PT Solution =Tt OPT + 2 * OPT,近似算法2 每次选择一个未安排的工作中用时童多的, 将它安排在当 前奂载最小的机器上,这是一个1.5倍近似算法,例2： K-Center Problem 问题描述：,1. 给定一张图G(V,E)满足G是metric 2. 要求选择k个点作为图的中心 3. 目标：最小化 radius = max dist(v, C) veV (ps : dist(v, C) = min dist(v,u) ueC,1. C =v v为图中任意点 2. for i=2 to k,choose Vj s.t. Dist(Vj,Cj.i) is largest cg+Vj,例3: Set Cover 算法： Greedy-Set-Cover (X, F) 1 U = X 2 = 0 3 while U 0 4 select an S e 尹 that maximizes |S A t/| 5 U = U-S 6 f f uS 7 return 弋,例4： Weighted Set Cover 问题插述: Set Cover的加强，每个subset从花 挽都暮1变为花费为Wj,每次选择subset Sj且使得W/ # of uncovered elements covered by Sj最小 THM:上述算法是一个Hn近似算法 (Ps： Hn=1+1/2+1/3+.+1/n),每次选择subset Sj且使得W/ # of uncovered elements covered by Sj最小 THM:上述算法是一个Hn近似算法 (Ps： Hn=1+1/2+1/3+.+1/n),证明： 假设我们 选择的subsets , Sit,根据我们算法选择subset的规则，我们有:,I,吧+i OPT,-m为第t次后未被覆盖的结点数）i,tt,证明(婕):那么我们才 Solution =吧+.+叱1 OPT(- + + . +-%-) 71 71 X n X . X 1 1 i r1 OPT(- + + . + 1) n n-1 =OPT * Hr,例5： Edge Disjoint Path(EDP) 问题描述: 给定一个无向图G(V,E) 给定一组二充组 T=(s ,t),(Sk，tQ 目标：寻找尽可为皂多的不相交道路T吏,得这些道路起终点为给定二充组。

算法 网络流? 不行 3 网 络流无法保证S j以Tj为 终点,3寻找近似算法,repeat pick an index i s.t. the shortest path Pj from Sjto & is shortest delete P)from the graph THM：这个算法是一个 S 近似算法,例5：背包问题 算法：对于给定的常数c,Pi,在改变价值的情况下用DP解决 (polytime), 得到Soltuion,在未改变的情况中 选择Solution中的 无素得到我们的近似解,THM :这是一个（1+c）近似算法,Thank you,更多的问题: .旅彳亍商问题 最大割问题,斯特林树问题,。