[+] Inapproximability Intro. NP optimization problem, approximation, PTAS, APX, LogAPX, PolyAPX, PTASreduction, APreduction, strictreduction, Areduction, Lreduction, APXhard. Max E3SATE5, Max 3SAT3, independent set, vertex cover, dominating set.  [Scribe Notes] [src]  
This lecture begins a series on inapproximability — proving the impossibility of approximation algorithms. I'll give a brief overview of most of the typical approximation factor upper and lower bounds in the world of graph algorithms. Then we'll introduce a bunch of general concepts, including new complexity classes (NPO, PTAS, APX, LogAPX, etc.) and stronger notions of reductions that preserve approximability (PTAS, AP, strict, A, and Lreductions). Finally, we'll prove APXhardness for a bunch of APXcomplete problems:

Handwritten notes, page 1/9 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/9 • [previous page] • [next page] • [PDF] 

Slides, page 1/5 •
[previous page] •
[next page] •
[PDF]
Slides, page 1/5 • [previous page] • [next page] • [PDF] 
The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.