Finding Best LP Relaxations for Various Cut Problems

on YouTube ↗26m

" summary

Proposes an estimation algorithm that, for fixed demand graph H, enumerates unambiguous supergraph F choices and returns the minimum standard flow‑LP value LP_F(G); proves this value lies between OPT(H,G) and the usual flow LP and is unique‑games hard to beat, so no stronger relaxation helps under UG. Uses dictator‑test reductions (hypercube gadgets) for hardness, shows directed bipartite H makes the flow LP optimal, and gets an FPT runtime in K with concrete consequences like a 1.3 approximation for undirected fixed‑H cases (using K^K time).

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:18People & Papers
3. 1:58Directed Multicut (before 2017)
4. 3:52In 2017
5. 6:07Multicut(H)
6. 8:43Flow-Cut (Distance) LP
7. 9:30LP Gap
8. 10:28Dictator Test
9. 11:18Reduction from UG
10. 12:56General H
11. 18:24Best (estimation) Algorithm
12. 19:56Undirected Analog
13. 21:23Global Cut Problems
14. 22:56Hardness Framework
15. 24:11Open Problems
16. 25:52Thank you!