The FPTAS for knapsack works by scaling down item profits by a factor that depends on epsilon and n, then running exact dynamic programming on the scaled instance. What determines the scaling factor and why does it produce polynomial running time?
AScale all profits to lie in [0, 1]; running time becomes O(n)
BScale profits by dividing by K = (epsilon * p_max) / n, round down to integers, then run DP on scaled profits. The maximum scaled profit is n/epsilon, so the DP table has O(n^2/epsilon) entries, making total time O(n^2/epsilon) — polynomial in both n and 1/epsilon
CScale profits to powers of 2; running time becomes O(n log P)
DNo scaling is needed — standard DP is already polynomial in 1/epsilon
The standard DP for knapsack runs in O(nP) time where P is the sum of all profits — pseudopolynomial because P can be exponential in the input size. The FPTAS scales profits by K = epsilon * p_max / n, rounding each profit down to floor(p_i / K). The maximum scaled profit is p_max / K = n/epsilon, so the DP table has dimensions n × (n/epsilon), giving O(n^2/epsilon) time. The rounding introduces at most K additive error per item, and at most nK = epsilon * p_max total error, which is at most epsilon * OPT (since OPT >= p_max). This yields a (1-epsilon)-approximation in polynomial time.
Question 2 True / False
Every problem that admits a PTAS also admits an FPTAS.
TTrue
FFalse
Answer: False
This is a common misconception. A PTAS allows running time like O(n^(1/epsilon)) — polynomial in n for fixed epsilon, but exponential in 1/epsilon. An FPTAS requires time polynomial in BOTH n and 1/epsilon. Strongly NP-hard problems (where the problem remains NP-hard even when all numbers are bounded by a polynomial in n) cannot have an FPTAS unless P = NP, because the FPTAS would solve the bounded-number version exactly by choosing epsilon < 1/n^c. Bin packing and Euclidean TSP have PTAS but no FPTAS (unless P = NP). The knapsack problem is only weakly NP-hard, which is why it admits an FPTAS.
Question 3 Short Answer
Arora's PTAS for Euclidean TSP achieves (1+epsilon)-approximation in n^O(1/epsilon) time. Explain why this is a PTAS but not an FPTAS, and what structural property of Euclidean space makes a PTAS possible when general TSP cannot be approximated within any constant factor.
Think about your answer, then reveal below.
Model answer: The running time n^O(1/epsilon) is polynomial in n for any fixed epsilon (e.g., epsilon = 0.01 gives n^O(100)), but it is exponential in 1/epsilon, so it is not an FPTAS. The structural property that enables a PTAS is the geometry of Euclidean space: the triangle inequality ensures that 'detours' are bounded, and Arora's algorithm exploits this by partitioning the plane into a randomly shifted quadtree, finding the optimal tour within each cell, and patching cells together. The random shift ensures that the patching cost is small in expectation. General (metric) TSP has a constant-factor approximation (Christofides' 3/2) but general (non-metric) TSP cannot be approximated within any polynomial factor unless P = NP, because approximating it would solve Hamiltonian Cycle.
The distinction between PTAS and FPTAS is not just theoretical — the practical difference between n^100 and n^2 * 100 is enormous. Arora's result is remarkable precisely because it shows Euclidean structure can be exploited for arbitrarily good approximation, despite TSP being NP-hard.
Question 4 True / False
A problem that is strongly NP-hard cannot have a pseudopolynomial-time algorithm unless P = NP.
TTrue
FFalse
Answer: True
A pseudopolynomial algorithm runs in time polynomial in the numeric value of the input (not its bit length). If a problem is strongly NP-hard, it remains NP-hard even when all numbers are bounded by a polynomial in n — so a pseudopolynomial algorithm would be truly polynomial on these bounded instances, implying P = NP. Since an FPTAS for a number problem implies a pseudopolynomial algorithm (set epsilon = 1/(max_value + 1) to get exact solutions), strongly NP-hard problems cannot have FPTAS either. This is the key connection: weak NP-hardness (like knapsack) allows FPTAS; strong NP-hardness (like bin packing) blocks it.