Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization |
| |
Authors: | S Thomas McCormick Satoru Fujishige |
| |
Institution: | (1) Sauder School of Business, University of British Columbia, Vancouver, BC, V6T 1Z2, Canada;(2) Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan |
| |
Abstract: | Bisubmodular functions are a natural “directed”, or “signed”, extension of submodular functions with several applications.
Recently Fujishige and Iwata showed how to extend the Iwata, Fleischer, and Fujishige (IFF) algorithm for submodular function
minimization (SFM) to bisubmodular function minimization (BSFM). However, they were able to extend only the weakly polynomial
version of IFF to BSFM. Here we investigate the difficulty that prevented them from also extending the strongly polynomial
version of IFF to BSFM, and we show a way around the difficulty. This new method gives a somewhat simpler strongly polynomial
SFM algorithm, as well as the first combinatorial strongly polynomial algorithm for BSFM. This further leads to extending
Iwata’s fully combinatorial version of IFF to BSFM.
The research of S. T. McCormick was supported by an NSERC Operating Grant.
The research of S. Fujishige was supported by a Grant-in-Aid of the Ministry of Education, Culture, Science and Technology
of Japan. |
| |
Keywords: | Mathematics Subject Classification (2000)" target="_blank">Mathematics Subject Classification (2000) Primary: 65K05 Secondary: 90C27 68W40 |
本文献已被 SpringerLink 等数据库收录! |
|