6.5440 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2023)

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

We'll briefly compare L-reductions to gap-preserving reductions. Gap-preserving reductions are generally easier, because they let us compare to the ideal solution (instead of an unknown optimal solution). They also imply a stronger form of hardness to approximate: hardness for a specific gap, instead of hardness of solving all gaps simultaneously. The only downside to gap-preserving reductions is that they do not establish APX-hardness, which is useful from a complexity-class perspective. L-reductions do this, but are rather difficult to obtain because in particular they require preserving optimal solutions, not just ideal solutions.