Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Polynomial-time approximation scheme
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a> (particularly <a href="/facts/Algorithmics/5k63DKM1">algorithmics</a>), a polynomial-time approximation scheme (PTAS) is a type of <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithm</a> for <a href="/facts/Optimization_problem/QzwJfFEE">optimization problems</a> (most often, <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a> optimization problems). </p><p>A PTAS is an algorithm which takes an instance of an optimization problem and a parameter ε > 0 and produces a solution that is within a factor 1 + ε of being optimal (or 1 – ε for maximization problems). For example, for the Euclidean <a href="/facts/Traveling_salesman_problem/2WEKVLnV">traveling salesman problem</a>, a PTAS would produce a tour with length at most (1 + ε)<i>L</i>, with L being the length of the shortest tour. </p><p>The running time of a PTAS is required to be polynomial in the problem size for every fixed ε, but can be different for different ε. Thus an algorithm running in time <i><a href="/facts/Big_O_notation/weFFjSWg">O</a></i>(<i>n</i>1/ε) or even <i>O</i>(<i>n</i>exp(1/ε)) counts as a PTAS. </p>