The last strategy lets the caller choose the accuracy. Scale the knapsack's values down by a factor tuned to epsilon, solve the scaled instance exactly with the value table from the dynamic programming course, and read the chosen items back at their original prices: the loss is at most epsilon times the optimum. On the loaded instance the promise is 193.5 and the realised loss is 0, and the table is 238 cells against the exact table's 3604.
Core ideas
The first idea is what a scheme is, as opposed to a fixed guarantee. The second is why scaling the values is the right thing to coarsen. The third is the reason a scheme exists for this problem and not for the travelling salesman.
Vertex cover's factor of 2 and greedy set cover's H_n are fixed by the algorithm. An approximation scheme takes ε > 0 as a parameter and returns an answer within a factor 1 + ε of the optimum; it is fully polynomial when the running time is polynomial in the input size and in 1/ε together. So the caller names the accuracy and pays for it, and the panel prints both halves of that trade as two columns of integers.
The knapsack has a table indexed by achievable value, whose size is the sum of the values, and that is the quantity making it pseudo-polynomial. Divide every value by K = ε · vmax / n and round down, and the table shrinks by a factor of about K. Rounding down loses less than K per item and at most n · K = ε · vmax in total; since the best single item fits, vmax ≤ OPT, so the loss is at most ε · OPT. Every one of those quantities is an exact fraction on the panel, so the promise is a number and the loss is compared against it.
This works because the knapsack is only weakly NP-hard: it has an algorithm polynomial in the magnitude of its numbers, and the scheme's whole job is to make the numbers small enough for that algorithm to be affordable. A strongly NP-hard problem has no such algorithm to shrink into, and the travelling salesman has no constant-factor approximation at all without a hypothesis. The digit-table reduction earlier on this course is the same distinction seen from the other side.
The material
What a scheme is, how the scaling works, the proof of the loss bound, what the lab measured at one epsilon and across six, and the instance where the scheme is a net loss.
A polynomial-time approximation scheme is a family of algorithms, one per ε > 0, each running in time polynomial in the input size and returning a value within 1 + ε of the optimum. It is fully polynomial when the running time is also polynomial in 1/ε, so that halving the error does not square the cost.
The last step is the one to get right. The answer is the set, not the scaled number: reporting the scaled optimum would report a value in the wrong units and it is the standard way an approximation scheme comes out looking wrong. The guarantee is about the original value of the chosen set.
Let S be the set the scaled table chooses and S* an optimal set for the original instance. Then the original value of S is at least OPT - ε · OPT.
Write v' for the scaled values. For any item, K · v'(i) ≤ v(i) < K · v'(i) + K, so scaling then rescaling loses less than K per item.
S is optimal for the scaled instance, so v'(S) ≥ v'(S*). Multiplying by K and using the two inequalities, the original value of S is at least K · v'(S) ≥ K · v'(S*) > v(S*) - |S*| · K ≥ OPT - n · K.
Now n · K = ε · vmax, and vmax ≤ OPT because the single most valuable item is a feasible solution on its own — assuming it fits, which items too heavy to fit are discarded first to ensure. So the loss is at most ε · OPT.
□
The instance is six items 3:520, 4:610, 5:805, 2:311, 6:902, 4:455 with capacity 12, and epsilon at 1/10. The largest value is 902 and there are six items, so K = 902/60 = 451/30, about 15.033. The scaled values are 34, 40, 53, 20, 60 and 30. The scaled table chooses the first three items, whose original value is 1935 — exactly the optimum. The promised loss is ε · OPT = 387/2, that is 193.5, and the realised loss is 0.
The cost side is the other column. The exact table is indexed by value from 0 to the sum of the values, which is 3603, so 3604 cells. The scaled table needs 238. That is the whole trade: a promise of losing up to a tenth of the optimum, bought with a table one fifteenth the size, and on this instance the promise was not called in at all.
The panel sweeps ε = 1, 1/2, 1/4, 1/8, 1/16 and 1/32 and prints the cells and the loss at each: 24, 47, 95, 190, 382 and 765 cells, with a realised loss of 0 at every one. The cells roughly double as epsilon halves, which is what “polynomial in 1/ε” looks like as integers, and the loss column stays at zero because this instance is kind. A promise is an upper bound on the loss and this one is never reached.
Switch to the five small items 3:5, 4:6, 5:8, 2:3, 6:9 with capacity 10 — the instance the branch-and-bound page used. The exact table has 32 cells. At epsilon one tenth, K = 9/50, which is less than 1, so dividing by it makes the values BIGGER: the scaled values are 27, 33, 44, 16, 50 and the scaled table needs 171 cells. The scheme is a fivefold loss, and the answer is the exact optimum either way.
This is worth more than a footnote. An approximation scheme is an asymptotic device: its saving comes from large values, and on small ones the scaling is counterproductive rather than merely useless. The cell counts say so, and nothing about the complexity class does. It is also a clean instance of the hazard this Subject is built around, in the direction people do not expect — the asymptotically better method losing on the instance on screen.
One more reading from the same sweep, on that small instance: at ε = 1 the scheme returns 15 against an optimum of 16, a loss of 1 inside a promise of 16, and at every smaller epsilon it returns 16 exactly. So the only epsilon at which the promise was ever needed is the one nobody would choose.
Interactive
Scale the values down, solve the scaled instance exactly, and lose at most ε × the optimum — with ε a fraction, so the promise is a number
Method
Five steps, two of which are measurements you should take before believing the scheme is worth running.
Epsilon is a business decision, not a mathematical one: it says how much value you are willing to leave on the table. Write it as an exact fraction, because the scale factor, the promise and the loss are all computed from it and a rounded epsilon makes a promise that is not quite the one you were given.
K = ε · vmax / n. The largest value is what sets the coarseness, so one enormous item coarsens every small one — the panel has an instance where a single item of 900 scales five values into 0, 1, 1, 2 and 0.
Run the value-indexed table on the scaled values and record which items it took. Then value that set at the original prices. Reporting the scaled optimum is reporting a number in units nobody asked about.
Two comparisons, both available on small instances: the loss against ε · OPT, and the size of the scaled table against the size of the exact one. The first says whether the guarantee held; the second says whether it was worth having.
If K < 1 the scaled values are larger than the originals and the table grows. That happens whenever ε · vmax < n, which on small instances is easy to arrange by accident, and the panel's small example is exactly that case.
Items 3:520, 4:610, 5:805, 2:311, 6:902, 4:455, capacity 12. The largest value is 902 and there are six items, so at ε = 1/10 the scale factor is 902/60 = 451/30.
The cells double as epsilon halves and the loss column never moves off zero. Both halves of that are worth noticing: the doubling is the 1/ε in the running time appearing as integers, and the zeros are this instance being kind. A promise is an upper bound on the loss, and a page reporting only the promise would have told you nothing about what actually happened.
At ε = 1 the table has 24 cells and still finds the optimum, which looks like the scheme being free. It is not a general fact: on the five-item instance from the branch-and-bound page, ε = 1 loses 1 against an optimum of 16. The difference is that here the rounding happens not to change which set the table chooses, and there is no way to know that without computing it.
For a faded rehearsal, load the instance with one dominant value — 5:900 among five small items — and predict the scale factor before running it. The supplied first move: vmax is 900 and there are six items, so at one tenth K is 15. Say what that does to a value of 11, and then check the scaled column — and notice which items become indistinguishable from nothing.
You should be able to compute K from epsilon, the largest value and the item count, scale and round the values, solve the scaled instance, re-value the chosen set at the original prices, compare the realised loss against ε · OPT, and compare the two table sizes before deciding the scheme was worth running.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.