Many problems of practical significance are NPcomplete but are too important to abandon merely because obtaining an optimal solution is intractable (khó). If a problem is NP-complete, we are unlikely to find a polynomial time algorithm for solving it exactly, but it may still be possible to find near-optimal solution in polynomial time. | Chapter 8 Approximation Algorithms Outline Why approximation algorithms? The vertex cover problem The set cover problem TSP Why Approximation Algorithms ? Many problems of practical significance are NP-complete but are too important to abandon merely because obtaining an optimal solution is intractable (khó). If a problem is NP-complete, we are unlikely to find a polynomial time algorithm for solving it exactly, but it may still be possible to find near-optimal solution in polynomial time. In practice, near-optimality is often good enough. An algorithm that returns near-optimal solutions is called an approximation algorithm. Performance bounds for approximation algorithms i is an optimization problem instance c(i) be the cost of solution produced by approximate algorithm and c*(i) be the cost of optimal solution. For minimization problem, we want c(i)/c*(i) to be as small as possible. For maximization problem, we want c*(i)/c(i) to be as small as possible. An approximation . | Chapter 8 Approximation Algorithms Outline Why approximation algorithms? The vertex cover problem The set cover problem TSP Why Approximation Algorithms ? Many problems of practical significance are NP-complete but are too important to abandon merely because obtaining an optimal solution is intractable (khó). If a problem is NP-complete, we are unlikely to find a polynomial time algorithm for solving it exactly, but it may still be possible to find near-optimal solution in polynomial time. In practice, near-optimality is often good enough. An algorithm that returns near-optimal solutions is called an approximation algorithm. Performance bounds for approximation algorithms i is an optimization problem instance c(i) be the cost of solution produced by approximate algorithm and c*(i) be the cost of optimal solution. For minimization problem, we want c(i)/c*(i) to be as small as possible. For maximization problem, we want c*(i)/c(i) to be as small as possible. An approximation algorithm for the given problem instance i, has a ratio bound of p(n) if for any input of size n, the cost c of the solution produced by the approximation algorithm is within a factor of p(n) of the cost c* of an optimal solution. That is max(c(i)/c*(i), c*(i)/c(i)) ≤ p(n) Note that p(n) is always greater than or equal to 1. If p(n) = 1 then the approximate algorithm is an optimal algorithm. The larger p(n), the worst algorithm Relative error We define the relative error of the approximate algorithm for any input size as |c(i) - c*(i)|/ c*(i) We say that an approximate algorithm has a relative error bound of ε(n) if |c(i)-c*(i)|/c*(i)≤ ε(n) 1. The Vertex-Cover Problem Vertex cover: given an undirected graph G=(V,E), then a subset V V such that if (u,v) E, then u V or v V (or both). Size of a vertex cover: the number of vertices in it. Vertex-cover problem: find a vertex-cover of minimal size. This problem is NP-hard, since the related decision problem is .
