Combinatorial Polynomial Algorithms for Skew Bisubmodular Function Minimization

Explore a 30-minute lecture on combinatorial polynomial algorithms for skew bisubmodular function minimization, presented by Satoru Fujishige at the Hausdorff Center for Mathematics. Delve into the concept of skew bisubmodularity, introduced by Huber, Krokhin, and Powell in 2013 as a generalization of bisubmodularity. Learn about the oracle tractability of minimizing skew-bisubmodular functions and the min-max theorem characterizing this minimization. Discover new combinatorial polynomial algorithms adapted from bisubmodular function minimization techniques, including novel concepts such as augmenting-path sequences and methods for handling auxiliary networks and conditioning graphs. Gain insights into this joint work with Shin-ichi Tanigawa, presented as part of the Hausdorff Trimester Program on Combinatorial Optimization.