Deeparnab Chakrabarty: Provable Submodular Function Minimization via Fujishige Wolfe Algorithm
798 views · Published 8 August 2016 · 3:02 · Indexed 29 October 2026
Channel: Microsoft Research · 2016 · Science & Technology
The Fujishige-Wolfe heuristic is empirically one of the fastest algorithms for Submodular Function Minimization and is based upon Wolfe's algorithm to find the nearest point on a polytope to the origin. There was no theoretical guarantees known for the same. In this work we give a convergence analysis for Wolfe's algorithm which implies a pseudo-polynomial running time for the Fujishige Wolfe algorithm.