optional · interactive figures

Explore: reductions and the FPTAS

The deck's 3-SAT gadget with the assignment in your hands, and the knapsack FPTAS with ε on a slider.

optional: nothing in the lab depends on itback to the slides

22 · explore

The gadget, with your assignment

Try: set x₂ = false with x₁ = true, x₃ = true, then flip x₃. Static versions: the reduction, the gadget on the example.

What it shows. The graph the reference sat_to_vertex_cover builds for $(x_1 \lor \lnot x_2 \lor x_3) \land (\lnot x_1 \lor x_2 \lor \lnot x_3)$: a top edge per variable, a triangle per clause, and a thin link from each corner to its literal. For each of the 8 assignments the page shows the vertex set the forward rule takes: the true literals, and in each triangle every corner but one whose literal is true.

For the 6 satisfying assignments this is the reference cover_from_assignment: 7 vertices, every edge covered.
For the 2 others (x₁ true, x₂ false, x₃ true; and x₁ false, x₂ true, x₃ false) one clause has no true literal. The same rule still takes 7 vertices, and one link is left uncovered, in red: no choice of 7 vertices can cover this graph along those lines.

Data: slides/viz/traces/u22.py; the minimum cover (7, over 4096 sets) is unit 00's brute_force.

22 · explore

The FPTAS, with ε on a slider

Try: slide ε from 0.05 up to 2 and watch which items are picked and how small the value table gets. Static version: the FPTAS on four items.

What it shows. The deck's four items (capacity 24) through the reference knapsack_fptas at 22 values of ε, against the exact knapsack_by_value (57, items 0, 2, 3). For each ε: the scale $K = \varepsilon v_{\max}/n$, the rounded values, the items the DP returns, the true value, the size of the rounded value table, and the proof's floor $\mathrm{OPT} - nK$.

Up to ε = 0.45 the rounding is fine enough to keep the optimum.
At ε = 0.5 (the deck's slide) rounding ties $\{0,2,3\}$ with $\{1,3\}$ and the DP returns the lighter one, 53.
At ε = 0.55 it is back to 57: rounding is not monotone, only the guarantee is.
From ε = 1 on the promised ratio $1 - \varepsilon$ says nothing, and the proof's floor $\mathrm{OPT} - nK$ is down to 1 at ε = 2, yet the answer stays decent: 53, then 44.