Reading Order
This map covers the substantive material in effalg-approx-April14-a.pdf, slides 31–41. The March 26 LP formulation is included only as background in the MaxSAT algorithm note.
| Slides | Subject | Note |
|---|---|---|
| 31 | Best-of-two MaxSAT, guarantee, derandomisation | best-of-two algorithm |
| 32–33 | Ten-clause gadget and Max2SAT inapproximability | MaxE3SAT to Max2SAT |
| 34 | L-reduction: instance conversion, solution conversion, two constants | linear reduction |
| 35 | Transfer of approximation hardness; exact hardness as the ratio- case | inapproximability transfer |
| 36–37 | Conditional Vertex Cover example; gap-introducing reductions | gap-introducing reduction |
| 38–39 | Transport an existing gap to another problem | gap-preserving reduction |
| 40 | Compose gap introduction and gap preservation | composition of gap reductions |
| 41 | Recap of the techniques and hardness framework | The linked notes above; earlier greedy and knapsack algorithms are recap references, not new material in this PDF. |
For a first reading, start with the Max2SAT, Max3SAT, and MaxE3SAT problem definitions. Read the concrete ten-clause construction before the general L-reduction theorem.
Two Ways to Transfer Hardness
- L-reductions: convert an arbitrary target solution back and control its error relative to the source optimum.
- Gap reductions: separate yes- and no-optima, then show that a good approximation would distinguish the two cases.
Both arguments assume a hypothetical target approximation and use it to solve a source problem known to be hard. The source of the contradiction must always be stated; constructing a map alone is not a hardness proof.