# 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 17 Video     [previous] [next] [completion form]

 [+] 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, This lecture beings with a bunch more L-reductions to prove various problems APX-complete: Max 2SAT Max NAE 3SAT Max cut (max positive 1-in-2SAT) Max 3-dimensional matching Edge matching puzzles (maximize number of matches) 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 Dominating set Token reconfiguration puzzles I'll also briefly mention the higher end of the approximation spectrum: 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
 No support for video detected. Please use an HTML5 browser. Download Video: 360p, 720p Handwritten notes, page 1/10 • [previous page] • [next page] • [PDF] Handwritten notes, page 1/10 • [previous page] • [next page] • [PDF] Slides, page 1/11 • [previous page] • [next page] • [PDF] Slides, page 1/11 • [previous page] • [next page] • [PDF]