Duality 2

on YouTube ↗01h 02m

" summary

Shows that semidefinite programming exactly captures the stable set polytope for perfect graphs (theta body = STAB for perfect graphs) and describes two ways to recover a maximum stable set from an SDP solution, including an algorithmic Carathéodory-style decomposition and eigenvalue/kernel-based rounding. Surveys applications: an SDP gives a 0.878 approximation for Max-Cut, metric-cone LP plus L1 embedding yields a log n loss for Sparsest Cut, and complex SDP improves guarantees for Max 3‑Cut; integrality gaps and embeddability limits are quantified.

AI-written summary · about

" chapters (34)

1. 0:00Introduction
2. 1:02Weighted stable sets
3. 2:14Recovering stable sets
4. 3:44Decomposition methods
5. 5:04Carathéodory's theorem
6. 7:24SDP face optimization
7. 9:48Edge-based decomposition
8. 11:18Small support theorems
9. 12:27Polyhedra directions
10. 14:22Matroid theory
11. 17:13Matroid polytopes
12. 18:57Matroid face structure
13. 20:42Negative correlation
14. 23:18Algorithm application
15. 24:53Kirszbraun theorem
16. 26:53Kirszbraun algorithmic
17. 31:25SDP in optimization
18. 33:54Max-cut problem
19. 35:23Sparse-cut problem
20. 37:01Cut cone definition
21. 38:42Metric cone embedding
22. 40:37L1 metric decomposition
23. 42:44Approximation ratio
24. 44:26Cut cone properties
25. 45:36Negative type metrics
26. 46:56L2 embedding
27. 48:22Metric cone dual
28. 50:29SDP rounding
29. 51:58Integrality gap
30. 53:30Approximation bounds
31. 55:12Max-3-cut problem
32. 57:57Complex SDP
33. 59:20Final remarks
34. 1:00:49Q&A

" related talks

• 44mCombinatorial Characterizations in Semidefinite Programming Duality: ...Gabor Pataki · Hyperbolic Polynomials and Hyperbolic Programming
• 32mLocal Statistics, Semidefinite Programming, and Community DetectionJess Banks · Computational Phase Transitions (Simons Institute, 2020)
• 42mTight Semidefinite Programming Relaxations for Polynomial OptimizationJiawang Nie · Hyperbolic Polynomials and Hyperbolic Programming
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 52mConstrained Subset Selection Problems under Diversity MeasuresMohit Singh · Hyperbolic Polynomials and Hyperbolic Programming
• 46mFaster SDP Hierarchy Solvers for Local Rounding AlgorithmsAli Sinop · Semidefinite Optimization, Approximation and Applications 2014
• 47mSuccinct Representations and Efficient Algorithms Based on Linear ProgrammingSudipto Guha · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)