Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Subexponential LPs Approximate Max-Cut

IEEE via YouTube

Overview

Explore a groundbreaking approach to approximating the Max-Cut problem using subexponential linear programs in this 26-minute IEEE conference talk. Delve into combinatorial optimization, linear and semidefinite programming, and their comparative analysis. Learn how LPs can effectively approximate Max Cut and examine additional discrete optimization problems. Follow the speakers through an engaging narrative, including a plot twist involving refutation in pseudorandom graphs, before reaching the conclusion of LP approximation in any graph. Gain insights from a high-level proof overview and walk away with a deeper understanding of this innovative solution in graph theory and optimization.

Syllabus

Intro
Combinatorial Optimization
Linear & Semidefinite Programs
Comparing LPs and SDPS
Case Study: Max Cut
LPs Can Approximate Max Cut!
Additional Discrete Optimization Problems
Story Time
Plot Twist: refutation in pseudorandom graphs
Conclusion: LP Approximation in any graph
High-level Proof Overview
Concluding

Taught by

IEEE FOCS: Foundations of Computer Science

Reviews

Start your review of Subexponential LPs Approximate Max-Cut

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.