PTAS and FPTAS

Core Idea

A Polynomial-Time Approximation Scheme (PTAS) is a family of algorithms parameterized by epsilon > 0, where each algorithm runs in polynomial time in n (for fixed epsilon) and returns a (1+epsilon)-approximate solution. An FPTAS (Fully Polynomial-Time Approximation Scheme) is stronger: the running time is polynomial in both n and 1/epsilon. The knapsack problem admits an FPTAS via scaling and rounding item profits, then applying dynamic programming — running in O(n^2/epsilon) time. PTAS existence versus FPTAS existence is a meaningful distinction: not all problems with a PTAS have an FPTAS, and the FPTAS exclusion is connected to strong NP-hardness. Problems like Euclidean TSP admit a PTAS (Arora, Mitchell) but are unlikely to have an FPTAS.

Explainer

Approximation algorithms give worst-case guarantees — a 2-approximation always returns a solution within a factor of 2 of optimal. But for many applications, you want to tune the accuracy: a 1.01-approximation for a shipping route, a 1.001-approximation for a portfolio allocation. Approximation schemes provide this tunability by parameterizing the accuracy with epsilon.

A PTAS is a family of algorithms indexed by epsilon > 0. For each epsilon, the algorithm runs in time polynomial in n (the input size) and returns a solution within factor (1+epsilon) of optimal. The catch is that the polynomial's degree or leading constant can depend on epsilon — a running time of O(n^(1/epsilon)) qualifies as a PTAS because for epsilon = 0.1 it is O(n^10), which is polynomial. But for epsilon = 0.001 it is O(n^1000), which is technically polynomial but practically useless. An FPTAS removes this catch: the running time must be polynomial in both n and 1/epsilon, like O(n^2/epsilon) or O(n^3/epsilon^2).

The knapsack FPTAS is the canonical example. The standard DP for knapsack runs in O(nP) time where P is the total profit — pseudopolynomial because P can be exponential in the input encoding. The FPTAS rescales profits by dividing by K = epsilon * p_max / n, effectively reducing the profit resolution. Rounding down to integers loses at most K profit per item, and with at most n items, the total loss is at most nK = epsilon * p_max <= epsilon * OPT. The scaled DP table has dimensions n by n/epsilon, giving O(n^2/epsilon) time. You trade a controlled amount of precision for a massive reduction in running time — from pseudopolynomial to fully polynomial.

The existence of an FPTAS is tied to the number-theoretic structure of the problem. Strongly NP-hard problems — those that remain NP-hard even when all numbers are polynomially bounded — cannot have FPTAS unless P = NP, because an FPTAS would solve the bounded case exactly. This is why knapsack (weakly NP-hard) has an FPTAS but bin packing (strongly NP-hard) does not. Problems like Euclidean TSP occupy an intermediate position: they admit a PTAS (using geometric structure) but the running time's dependence on 1/epsilon is exponential, and this is believed to be inherent. The PTAS / FPTAS / no-PTAS hierarchy provides a refined classification of NP-hard optimization problems by their approximability.