Traveling-salesman Problem The subset-sum problem ·旅行商问题:旅行商必须访问所有n个城 problem, we are given a 市,而每两个城市之间的的行走费用不 finite set S subset of N, and a target t in n 同,求一条费用最小的路径 we ask whether there is a subset s subset of TSP iS NP-complete S whose elements sum to t SUBSET-SUM=(<S, t, there exists a subset S of s such that t=∑sess SUBSET-SUM is NP-complete 清华大学宋域恒 请华大学宋恒 目前对NPC问题的处理 Approximation Algorithms 由于没有迹象表明NPC问题可以有多项 Optimization problem has a minimum or 式时间的算法,当然也没有证明它没 有。目前人们对于NPC问题主要是采取 denote as c 近似计算方法来解决这类问题 olution hence it computes an approximate va called C Performance ratios for approximation algorithm p(n) satisfies }≤p(mn) We call the algorithm is p(n)-approximation 清华大学末斌恒 algorithm 请华大学宋恒 Approximation scheme An approximation scheme for an optimization problem is an approximation algorithm that takes as input not only an instance of the problem, but so a value e >0 such scheme is a(1+e)-approximation algorithm Polynomial time approximation scheme Fully polynomial time approximation scheme 清华大学末域恒 请华大学宋10 清华大学 宋斌恒 55 Traveling-salesman Problem • 旅行商问题：旅行商必须访问所有n个城 市，而每两个城市之间的的行走费用不 同，求一条费用最小的路径 • TSP is NP-complete 清华大学 宋斌恒 56 The subset-sum problem • In the subset-sum problem, we are given a finite set S subset of N, and a target t in N, we ask whether there is a subset S’ subset of S whose elements sum to t. • SUBSET-SUM={<S,t>,there exists a subset S’ of S such that t = Σs∈S’ s} • SUBSET-SUM is NP-complete. 清华大学 宋斌恒 57 目前对NPC问题的处理 • 由于没有迹象表明NPC问题可以有多项 式时间的算法，当然也没有证明它没 有。目前人们对于NPC问题主要是采取 近似计算方法来解决这类问题， 清华大学 宋斌恒 58 Approximation Algorithms • Optimization problem has a minimum or maximum value(we assume it is positive), we denote as C • Approximation algorithm cannot get the optimal solution hence it computes an approximate value, called C*, • Performance ratios for approximation algorithms: ρ(n) satisfies • Max{C/C*, C*/C}≤ ρ(n) • We call the algorithm is ρ(n)-approximation algorithm 清华大学 宋斌恒 59 Approximation scheme • An approximation scheme for an optimization problem is an approximation algorithm that takes as input not only an instance of the problem, but also a value ε >0 such that for any fixed ε, the scheme is a (1+ε)-approximation algorithm • Polynomial time approximation scheme • Fully polynomial time approximation scheme 清华大学 宋斌恒 60