[+] 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.  
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] 