LP Relaxations for Valued CSPs

on YouTube ↗41m

" summary

Gives an exact algebraic characterization of when linear-program relaxations solve valued CSPs: the basic LP (BLP) or a bounded Sherali–Adams level is tight iff the language admits certain weighted polymorphisms (fractional, symmetric, or weak near-unanimity), leading to dichotomy theorems and polynomial algorithms for many finite-valued and conservative languages. Uses the BLP/SA hierarchy, algebraic clones and LP duality to build constructive algorithms and hardness reductions; notable collapse: constant levels (often k=2 or 3) suffice. Results are proved and decidability follows in key cases.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 1:20St Mean Cut
3. 2:43Vertex Cover
4. 4:11VC SPL
5. 7:50LP accessions
6. 13:09Relaxation
7. 13:33Question
8. 14:44Results
9. 16:48Polymorphisms
10. 18:51Weighted polymorphisms
11. 21:12Gamma functions
12. 23:59Submodular functions
13. 25:06Proof lifetime
14. 29:03Power of shell items
15. 31:31Proof
16. 34:10Conservative VCS
17. 35:17Minimum solution problems