Deeparnab Chakrabarty: Provable Submodular Function Minimization via Fujishige Wolfe Algorithm

Опубликовано 8 августа 2016, 23:11

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.