Spring 2007 Seminar Series

DATE: Thursday, February 22, 2007
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the Philip M. Morse Reading Room, E40-106

SPEAKER:
James Orlin

TITLE
A Faster and Simpler Strongly Polynomial Time Algorithm for Submodular Function Minimization

ABSTRACT
A submodular function f is a set valued function defined on a set V such that for all subsets S and T of V, f(S) + f(T) >= f(S union T) + f(S intersection T). We consider the problem of Submodular Function Minimization (SFM). We provide an overview on the significance of submodular function minimization in combinatorial optimization, and survey previous polynomial time algorithms for solving this problem. We also present a new algorithm that runs in O (n5 Q + n6) steps, where Q is the time it takes to evaluate f( ). The algorithm improves upon the best previous combinatorial strongly polynomial algorithm by a factor of n log n, and also strictly dominates the running time of the ellipsoid algorithm on SFM.