6.892 Algorithmic Lower Bounds: Fun with Hardness Proofs (Spring 2019)

Prof. Erik Demaine       TAs: Jeffrey Bosboom, Jayson Lynch


[Home] [Lectures] [Problem Sets] [Project] [Coauthor] [Accessibility]

Lecture 16 Video     [previous] [next] [completion form]

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

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]