Seminar - Christopher Price

Combinatorical algorithms for submodular function minimization and related problems

Abstract:

The submodular function minimization problem generalizes the classical minimum cut problem and contains a number of other well-known combinatorial optimization problems as special cases. This thesis concerns the submodular function minimization problem as well as two related problems: matroid polyhedron membership and matroid intersection. This talk will discuss algorithms for the latter problems, due to Cunningham. In particular, errors in the proofs of the running time bounds for these algorithms will be identied, and possible resolutions will be explored.