《NPC问题与近似算法》由会员分享，可在线阅读，更多相关《NPC问题与近似算法（33页珍藏版）》请在金锄头文库上搜索。
1、NPCNPC问题与近似算法问题与近似算法林衍凯林衍凯l定义: 如果一个问题Y可以通过调用问题X且通过poly-time的时间转化得到，我们称： DefinitionofNP-CompletenesslIf X is P, then Y is PIf X is P, then Y is PlIF Y is NP, then X is NPIF Y is NP, then X is NP DefinitionofNP-Completenessl Independent Set & Vertex Cover IS: If there is IS of G in size of =k VC: If t
2、here is IS of G in size of =kDefinitionofNP-CompletenessExample1：l Observation: S V is IS if and only if VS is VC of the graph Gl Conclusion： IS VC & VC ISDefinitionofNP-Completenessl Vertex Cover Set CoverSC: Given a set U of elements,a collection M of subset of U S1,S2Sn,and a integer k,ask if Def
3、initionofNP-CompletenessExample2：DefinitionofNP-Completeness我们怎样证明一个问题是我们怎样证明一个问题是NPC的呢的呢？l 定义： 如果问题X满足以下条件，那么X属于NPC。1. 2.对于任意DefinitionofNP-CompletenessReducibilityofNP-CompletenessReducibilityofNP-Completeness证明：明：The Clique Problem is Np-completeShow that a given clique can be checked in poly-tim
4、eShow that 3-CNF-SAT CliqueReducibilityofNP-Completeness令令 为一个一个k子句的子句的 3-CNF ，且且 我们如何构建一幅图G(V,E)将图的团和3-CNF问题联系起来？ReducibilityofNP-CompletenessReducibilityofNP-Completeness对于每个子句 ，我们在图中添加3个结点 ，如果结点 满足以下两个条件，就连边：1. 2. ApproximationAlgorithm例例1：Load Balancing Problem问题描述：1.给定个工作，工作需要时间tj，同时拥有m台机器。2.定义
5、机器i的负载为：3.定义总负载：4.目标：最小化总负载ApproximationAlgorithm近似算法近似算法1每次任意选择一个未安排的工作，将它安排在当前负载最小的机器上这是一个2倍近似算法ApproximationAlgorithm证明：证明：1. 2. 假设Mi 是负载最大的机器，工作j是机器i最后一个工作，我们有： ApproximationAlgorithm近似算法近似算法2每次选择一个未安排的工作中用时最多的，将它安排在当前负载最小的机器上这是一个1.5倍近似算法ApproximationAlgorithm例例2：K-Center Problem问题描述：1.给定一张图G(V,
6、E)满足 G 是metric2.要求选择k个点作为图的中心3.目标：最小化 ApproximationAlgorithm近似算法近似算法1每次假设图的radius（至多|E|个），然后执行以下算法:1.S=V C=empty2.While S!=emptychoose an arbitary v in SCC+v3. if |C|=k succeed else increase radiusApproximationAlgorithm近似算法近似算法21.C1 =v v 为图中任意点2.for i=2 to kchoose vi s.t. Dist(vi,Ci-1) is largestCiC
7、i-1+ViApproximationAlgorithm例例3：Set Cover算法：算法：ApproximationAlgorithm例例4：Weighted Set Cover问题描述：问题描述：Set Cover的加强，每个的加强，每个subset从花从花费都是费都是1变为花费为变为花费为WiApproximationAlgorithm近似算法近似算法每次选择subset Si且使得Wi/ # of uncovered elements covered by Si最小 THM: 上述算法是一个Hn近似算法（Ps：Hn=1+1/2+1/3+1/n)ApproximationAlgorit
8、hm贪心近似算法贪心近似算法每次选择subset Si且使得Wi/ # of uncovered elements covered by Si最小 THM: 上述算法是一个Hn近似算法（Ps：Hn=1+1/2+1/3+1/n)ApproximationAlgorithm证明：证明：假设我们选择的subset为根据我们算法选择subset的规则，我们有： 为第t次后未被覆盖的结点数）ApproximationAlgorithm证明（续）：那么我们有证明（续）：那么我们有ApproximationAlgorithm例例5：Edge Disjoint Path(EDP)问题描述：问题描述：给定一个无
9、向图G(V,E)给定一组二元组T=(s1,t1),(sk,tk)目标：寻找尽可能多的不相交道路使得这些道路起终点为给定二元组。ApproximationAlgorithm算法网络流？不行网络流无法保证Si以Ti为终点寻找近似算法ApproximationAlgorithm近似算法repeatpick an index i s.t. the shortest path Pi from si to tiis shortest delete Pi from the graphTHM：这个算法是一个 近似算法ApproximationAlgorithm例例5：背包问题：背包问题算法：对于给定的常数c, k=在改变价值的情况下用DP解决（polytime），得到SoltuionApproximationAlgorithm在未改变的情况中选择Solution中的元素得到我们的近似解THM：这是一个（1+c）近似算法Thank youApproximationAlgorithm更多的问题：旅行商问题最大割问题斯特林树问题
