25.7. 15:00 - Algebraic algorithms for special submodular function minimization

Universität Ulm

Vortrag "Algebraic algorithms for special submodular

function minimization" gehalten von Herr Prof. Dr. Rohit Gurjar

A real function defined over all subsets of a set is called submodular if it satisfies
a natural diminishing returns property, that is, the marginal value of an element
w.r.t. a set decreases as the set increases. Submodular function minimization has
a wide range of applications and has been extensively studied. The problem has
polynomial time algorithms but there seems to be no efficient parallel (NC)
algorithms known for it. We give an algebraic algorithm for minimizing special
kinds of submodular functions. These are functions which can be decomposed
into two monotone submodular functions each of which comes from the rank of a
collection of subspaces. The algebraic algorithm is parallelizable and puts this
case of submodular minimization into RNC.