|
|
|
|
|
Polynomial Time Approximation SchemeIn computer science, a polynomial time approximation scheme (abbreviated PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an instance of an optimization problem and a parameter ε>0 and produces a solution of an optimization problem that is within ε factor of being optimal. For example, for traveling salesman problem, a PTAS would produce a tour with length at most (1+ε)L, with L being the length of the shortest tour. The running time of a PTAS is required to be polynomial in n for every fixed ε but can depend arbitrarily on ε. Thus, an algorithm, running in time O(n1/ε) or even O(n21/ε) counts as PTAS. A related notion is fully polynomial time approximation scheme or FPTAS in which the running time is required to be O(nc) for a constant c independent of ε. The constant under big-O can still depend on ε arbitrarily. External link *A compendium of NP optimization problems - list which NP optimization problems have PTAS
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|