Problem setup

  • A knapsack of capacity W, and n items with weights w₁…wₙ and values v₁…vₙ 3:45.
  • Goal: pick a subset with total weight ≤ W maximizing total value 3:45.

The starting point: pseudo-polynomial DP

  • There is an exact dynamic program running in O(nV), where V = Σᵢ vᵢ 4:28, 4:58.
  • This is not polynomial time: the running time depends on the magnitude of the numbers, not their bit-length. Writing V takes only log V bits, so the input can be exponentially smaller than V 4:58.
  • Fix: make V small by rounding 5:17, 3:14.

The algorithm

  1. Define rounded values vᵢ′ = ⌊ (n/ε) · vᵢ / v_max ⌋ — i.e. scale by α = n / (ε·v_max) and floor to an integer 5:17, 5:47.
  2. Run the exact O(nV′) DP on the rounded instance; it returns a set A 5:47.
  3. Output A as the solution to the original instance 6:16.

Running-time bound

  • V′ ≤ n · maxᵢ vᵢ′, and since vᵢ ≤ v_max, each vᵢ′ ≤ n/ε 6:41.
  • So V′ ≤ n²/ε, giving total time O(nV′) = O(n³/ε) — polynomial in both n and 1/ε, hence an FPTAS 6:41.

Why the value is preserved

  • Pure scaling by a constant changes nothing: every set's value scales by the same factor, so the optimum is unchanged 8:36.
  • The floor is the only source of loss: each item loses at most 1 unit of rounded value, so any set S loses at most |S| ≤ n 8:17, 9:00.
  • OPT′ ≥ v′_max ≥ n/ε, because the item achieving v_max alone contributes that much 7:20, 7:47.
  • Hence the loss of at most n is at most ε · OPT′ 9:00.

Formal claim and proof sketch

Claim. If the DP on the rounded instance returns A ⊆ [n], then v(A) ≥ (1 − ε)·OPT for the original valuation 9:34.

Key inequalities, for every set S and scaling factor α = n/(ε·v_max) 10:13, 10:48:

α·v(S) − |S|  ≤  v′(S)  ≤  α·v(S)

Chain of the proof, with A* an optimal set for the original instance 10:48, 11:34:

  1. v(A) ≥ (1/α)·v′(A) — from the upper inequality 11:34.
  2. ≥ (1/α)·v′(A*) — A is optimal for the rounded values 11:51.
  3. ≥ (1/α)·(α·v(A*) − |A*|) = OPT − |A*|/α ≥ OPT − n/α 11:51, 12:32.
  4. n/α = ε·v_max by definition of α, and OPT ≥ v_max, so the result is ≥ (1 − ε)·OPT 13:14.

Best known bound for Knapsack

  • A different algorithm achieves O( n·log(1/ε) + 1/ε⁴ ), due to Lawler, 1979 2:18, 2:48.
  • The lecturer searched for post-1979 improvements and found none 2:48.