Owing to several applications in large scale learning and 
vision problems, fast submodular function minimization (SFM) has become a 
very important problem. Theoretically, unconstrained SFM is polynomial 
time solvable, however, these algorithms are not practical. In 1976, Wolfe 
proposed a heuristic for projection onto a polytope, and in 1980, 
Fujishige showed how Wolfe's heuristic can be used for SFM. For general 
submodular functions, this Fujishige-Wolfe heuristic seems to have the 
best empirical performance. Despite its good practical performance, very 
little is known about Wolfe's projection algorithm theoretically.

In this talk, I will describe the first analysis which proves that the 
heuristic is polynomial time for bounded submodular functions. Our work 
involves the first convergence analysis of Wolfe’s projection heuristic, 
and proving a robust version of Fujishige’s reduction theorem.