[+] Gap Inapproximability. Gap problem, gap-producing and gap-preserving reductions, PCP theorem, max E3-X(N)OR-SAT, max E3SAT, Label Cover (Max-Rep and Min-Rep), directed Steiner forest, node-weighted Steiner tree, Unique Games Conjecture. | |||||
This lecture is about gap problems: distinguishing between good and bad solutions, with a big gap in between those two notions. This perspective is particularly nice because we can turn NP-hardness of a decision problem into NP-hardness of approximation. It also often leads to tighter bounds on approximability. For example, we'll see a reduction that gives an optimal 7/8-inapproximability for Max E3SAT. A big tool here is the PCP (Probabilistically Checkable Proofs) theorem, which won a Gödel Prize in 2001. We'll see how gap problem hardness naturally leads to probabilistically checkable proofs and vice versa. Then we'll see the core PCP lower bound theorems, a problem called label cover (MinRep and MaxRep). Finally, we'll cover the Unique Games Conjecture, which (if true) leads to further improved inapproximability constants. |
Handwritten notes, page 1/7 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/7 • [previous page] • [next page] • [PDF] |
|
Slides, page 1/15 •
[previous page] •
[next page] •
[PDF]
http://erikdemaine.org/papers/Tetris_IJCGA/ (slide from Lecture 3) Slides, page 1/15 • [previous page] • [next page] • [PDF] |