Not every problem admits an approximation scheme

  • Set cover: you cannot beat a log n approximation. This is not merely an integrality-gap obstruction — there is a proof that beating it would let you solve SAT unexpectedly fast 14:25.
  • Vertex cover: a fixed constant > 1 is known such that, unless P = NP, you cannot beat that ratio; more recent evidence (under a conjecture) suggests you cannot beat the factor-2 approximation at all 14:25, 14:54.
  • Sometimes, though, the obstruction is much simpler than these hardness-of-approximation results 14:54.

Bin packing — the easy counterexample

Input: n items with sizes s₁…sₙ ∈ [0,1]; bins have capacity exactly 1; pack all items into as few bins as possible, without cutting items 15:14, 16:01, 16:44.

Known hardness: bin packing is NP-hard, and even the decision problem "can these items fit into 2 bins?" is NP-complete 16:44.

No FPTAS unless P = NP 18:32:

  1. Suppose an FPTAS exists, returning a packing with at most (1+ε)·OPT bins in time poly(n, 1/ε) 17:12, 17:50.
  2. Run it with ε ≪ 1/n. The additive error in the number of bins is then less than 1 18:32.
  3. The number of bins is an integer, so an answer of e.g. "2.2 bins" pins the truth down to exactly 2 18:32.
  4. That solves the NP-complete 2-bin decision problem in polynomial time 18:32.

Terminology

  • A problem with no FPTAS (under P ≠ NP) for this kind of reason is called strongly NP-hard 19:22.

The dual question: why doesn't this argument kill Knapsack?

An audience question raised the same integrality objection for Knapsack, whose optimum is also an integer when values are integers 30:51, 31:09:

  • Naive attempt: OPT ≤ n·v_max, so set ε ≪ 1/(n·v_max), run the FPTAS, round to an integer 31:34.
  • Why it fails: writing v_max takes only log v_max bits, so 1/ε is exponential in the input size — poly(1/ε) is not polynomial in the input 32:03.
  • The same escape applies to DNF counting: a DNF of size n can have exponentially many solutions, e.g. x₁ ∨ x₂ ∨ … ∨ xₙ has 2ⁿ − n satisfying assignments (only the all-false-ish cases fail), so a small enough ε would be exponentially expensive 32:03, 32:42.