6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall '14)
Prof. Erik Demaine TAs: Sarah Eisenstat, Jayson Lynch
Inapproximability Examples. Max 2SAT, max NAE 3SAT, max cut,
max/min CSP/ones characterization, max independent set,
max 3DM-E2, max edge matching puzzles. APX-intermediate.
Log-APX-complete: set cover, dominating set, token reconfiguration.
Poly-APX-complete: independent set, clique.
Exp-APX-complete: nonmetric Traveling salesman.
NPO PB-complete: independent dominating set, longest induced path.
NPO-complete: weighted SAT, 0-1 linear programming,
|| [Scribe Notes] [src]
This lecture beings with a bunch more L-reductions to prove
various problems APX-complete:
More generally, we'll see
a powerful characterization theorem
of when minimizing or maximizing the number of satisfied clauses or number of
true variables is approximable or inapproximable according to the
structure of those clauses (in the spirit of Schaefer's Dichotomy Theorem).
Next we'll also see some Log-APX-hardness, L-reducing from set cover to
I'll also briefly mention the higher end of the approximation spectrum:
- Max 2SAT
- Max NAE 3SAT
- Max cut (max positive 1-in-2SAT)
- Max 3-dimensional matching
- Edge matching puzzles (maximize number of matches)
- Poly-APX-complete: max independent set and clique
- Exp-APX-complete: nonmetric traveling salesman
- NPO PB-complete: longest induced path, longest path with forbidden pairs,
minimum independent dominating set, shortest computation
- NPO-complete: max/min weighted SAT — find a satisfying assignment
that maximizes/minimizes the sum of weights of true variables — and
max/min 0-1 linear programming
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,