Completed
LPs Can Approximate Max Cut!
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Subexponential LPs Approximate Max-Cut
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Combinatorial Optimization
- 3 Linear & Semidefinite Programs
- 4 Comparing LPs and SDPS
- 5 Case Study: Max Cut
- 6 LPs Can Approximate Max Cut!
- 7 Additional Discrete Optimization Problems
- 8 Story Time
- 9 Plot Twist: refutation in pseudorandom graphs
- 10 Conclusion: LP Approximation in any graph
- 11 High-level Proof Overview
- 12 Concluding
