Completed
Robust Fujishige's Theorem
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Provable Submodular Function Minimization via Fujishige Wolfe Algorithm
Automatically move to the next video in the Classroom when playback concludes
- 1 Submodular Functions
- 2 Submodular Function Minimization Find set A which minimizes f(A)
- 3 Theory vs Practice
- 4 Is it good in theory?
- 5 Base Polytope
- 6 Edmond's Theorems for Submod. f
- 7 Robust Fujishige's Theorem
- 8 Reduction to Convex Optimization
- 9 Geometrical preliminaries
- 10 Wolfe's algorithm in a nutshell
- 11 Checking Optimality
- 12 Wolfe's Algorithm: Details
- 13 If S is a corral: Major Cycle
- 14 Summarizing Wolfe's Algorithm
- 15 Two Major Cycles in a Row
- 16 Major-minor-Major
- 17 Wrapping up
- 18 Take home points
