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

Prof. Erik Demaine       TAs: Josh Brunner, Lily Chung, Jenny Diomidova

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

Lecture 18 Video     [previous] [next]

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

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]

http://dx.doi.org/10.1109/CCC.1997.612321

Slides, page 1/11 • [previous page] • [next page] • [PDF]

The video above should play if your web browser supports 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.