NPC问题与近似算法 林衍凯 Mrlyk423@gmail.com

Definition of NP-Completeness 定义: 如果一个问题Y可以通过调用问题X且通过poly-time的时间转化得到，我们称：

Definition of NP-Completeness If X is P, then Y is P IF Y is NP, then X is NP

Definition of NP-Completeness Example1： 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

Definition of NP-Completeness Observation: S V is IS if and only if V\S is VC of the graph G Conclusion： IS VC & VC IS

Definition of NP-Completeness Example2： Vertex Cover Set Cover SC: Given a set U of elements,a collection M of subset of U S1,S2…Sn,and a integer k,ask if

Definition of NP-Completeness

Definition of NP-Completeness 定义： 如果问题X满足以下条件，那么X属于NPC。 对于任意

Reducibility of NP-Completeness

Reducibility of NP-Completeness 证明： The Clique Problem is Np-complete Show that a given clique can be checked in poly-time Show that 3-CNF-SAT Clique

Reducibility of NP-Completeness 令 为一个k子句的 3-CNF ，且 我们如何构建一幅图G(V,E)将图的团和3-CNF问题联系起来？

Reducibility of NP-Completeness

Reducibility of NP-Completeness 对于每个子句 ，我们在图中添加3个结点 ，如果结点 满足以下两个条件，就连边：

Approximation Algorithm 例1：Load Balancing Problem 问题描述： 给定ｎ个工作，工作ｊ需要时间tj，同时拥有m台机器。 定义机器i的负载为： 定义总负载： 目标：最小化总负载

Approximation Algorithm 近似算法1 每次任意选择一个未安排的工作，将它安排在当前负载最小的机器上 这是一个2倍近似算法

Approximation Algorithm 证明： 假设Mi 是负载最大的机器，工作j是机器i最后一个工作，我们有：

Approximation Algorithm 近似算法2 每次选择一个未安排的工作中用时最多的，将它安排在当前负载最小的机器上 这是一个1.5倍近似算法

Approximation Algorithm 例2：K-Center Problem 问题描述： 给定一张图G(V,E)满足 G 是metric 要求选择k个点作为图的中心 目标：最小化

Approximation Algorithm 近似算法1 每次假设图的radius（至多|E|个），然后执行以下算法: S=V C=empty While S!=empty choose an arbitary v in S CC+v 3. if |C|<=k succeed else increase radius

Approximation Algorithm 近似算法2 C1 ={v} v 为图中任意点 for i=2 to k choose vi s.t. Dist(vi,Ci-1) is largest CiCi-1+Vi

Approximation Algorithm 例3：Set Cover 算法：

Approximation Algorithm 例4：Weighted Set Cover 问题描述： Set Cover的加强，每个subset从花费都是1变为花费为Wi

Approximation Algorithm 近似算法 每次选择subset Si且使得Wi/ # of uncovered elements covered by Si最小 THM: 上述算法是一个Hn近似算法 （Ps：Hn=1+1/2+1/3+…+1/n)

Approximation Algorithm 贪心近似算法 每次选择subset Si且使得Wi/ # of uncovered elements covered by Si最小 THM: 上述算法是一个Hn近似算法 （Ps：Hn=1+1/2+1/3+…+1/n)

Approximation Algorithm 证明： 假设我们选择的subset为 根据我们算法选择subset的规则，我们有： 为第t次后未被覆盖的结点数）

Approximation Algorithm 证明（续）：那么我们有

Approximation Algorithm 例5：Edge Disjoint Path(EDP) 问题描述： 给定一个无向图G(V,E) 给定一组二元组T={(s1,t1),…(sk,tk)} 目标：寻找尽可能多的不相交道路使得这些道路起终点为给定二元组。

Approximation Algorithm 算法 网络流？ 不行网络流无法保证Si以Ti为终点 寻找近似算法

Approximation Algorithm 近似算法 repeat pick an index i s.t. the shortest path Pi from si to ti is shortest delete Pi from the graph THM：这个算法是一个 近似算法

Approximation Algorithm 例5：背包问题 算法：对于给定的常数c, k= 在改变价值的情况下用DP解决（polytime），得到Soltuion

Approximation Algorithm 在未改变的情况中选择Solution中的元素得到我们的近似解 THM：这是一个（1+c）近似算法

Thank you

Approximation Algorithm 更多的问题： 旅行商问题 最大割问题 斯特林树问题