Jonathan Huggins : April 19

Submodularity part II, starting at 5:45pm.

After a brief review of two weeks ago, I will describe Queyranne's efficient and fully combinatorial algorithm for minimizing symmetric submodular functions. Next, I will give the details of the convex Lovasz extension of submodular functions, including a sketch of the proof of how to efficiently calculate the extension. Finally, I'll discuss portions of a recent paper on decomposable submodular functions by Stobbe and Krause, emphasizing its application to Markov Random Fields and the connections to the Lovasz extension and concave functions