Provable Submodular Function Minimization via Fujishige Wolfe Algorithm

Explore the Fujishige-Wolfe heuristic for Submodular Function Minimization in this 25-minute lecture from the Hausdorff Trimester Program on Combinatorial Optimization. Delve into the convergence analysis of Wolfe's algorithm and its implications for the pseudopolynomial running time of the Fujishige Wolfe algorithm. Examine key concepts such as the base polytope, Edmond's theorems, and the reduction to convex optimization. Learn about Wolfe's algorithm in detail, including major cycles, optimality checking, and the major-minor-major pattern. Gain insights into the theoretical guarantees and practical applications of this empirically fast algorithm for finding the nearest point on a polytope to the origin.

Submodular Functions
Submodular Function Minimization Find set A which minimizes f(A)
Theory vs Practice
Is it good in theory?
Base Polytope
Edmond's Theorems for Submod. f
Robust Fujishige's Theorem
Reduction to Convex Optimization
Geometrical preliminaries
Wolfe's algorithm in a nutshell
Checking Optimality
Wolfe's Algorithm: Details
If S is a corral: Major Cycle
Summarizing Wolfe's Algorithm
Two Major Cycles in a Row
Major-minor-Major
Wrapping up
Take home points