S. Thomas McCormick - University of British Columbia

Better Algorithms for Bisubmodular Function Minimization

Abstract: Bisubmodularity is a "signed" version of submodularity where an element can belong to a set positively or negatively. Minimizing bisubmodular functions (BSFM) is a common generalization of minimizing submodular functions, some problems in non-bipartite matching, and membership in convex jump systems. Fujishige and Iwata extended the weakly polynomial IFF algorithm for submodular function minimization (SFM) to the bisubmodular case. We develop a simpler version of the Fujishige-Iwata algorithm, and show how it extends when the bisubmodular function is defined only over a structured sub-family of signed sets (signed ring families). This then becomes the key building block to making a strongly polynomial BSFM algorithm, as well as faster and fully combinatorial versions.

Co-Author: Satoru Fujishige, Professor, Kyoto University, RIMS, Kyoto -- 606-8502, Japan, fujishig@kurims.kyoto-u.ac.jp

Colloquium - 16:00

cancelled -

Abstract: