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.