Deeparnab Chakrabarty: Provable Submodular Function Minimization via Fujishige Wolfe Algorithm

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.

Date:
Affiliation:
Microsoft Research

    • Portrait of Casey Anderson

      Casey Anderson

  • Research Area