[+] 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. |
Video Player is loading. This is a modal window. |
Handwritten notes, page 1/7 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/7 • [previous page] • [next page] • [PDF] |
Slides, page 6/15 •
[previous page] •
[next page] •
[PDF]
http://people.csail.mit.edu/dmoshkov/proj-games/index.html Slides, page 6/15 • [previous page] • [next page] • [PDF] |