6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall '14)

Prof. Erik Demaine     TAs: Sarah Eisenstat, Jayson Lynch


[Home] [Lectures] [Problem Sets] [Project] [Open Problems] [Piazza]

Lecture 10 Video     [previous] [next]

[+] Inapproximability Intro. NP optimization problem, approximation, PTAS, APX, Log-APX, Poly-APX, PTAS-reduction, AP-reduction, strict-reduction, A-reduction, L-reduction, APX-hard. Max E3SAT-E5, Max 3SAT-3, 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, Log-APX, etc.) and stronger notions of reductions that preserve approximability (PTAS-, AP-, strict-, A-, and L-reductions). Finally, we'll prove APX-hardness for a bunch of APX-complete problems:

  • Max 3SAT-3
  • Independent set
  • Vertex cover
  • Dominating set

Download Video: 360p, 720p

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.