Polynomial combinatorial algorithms for skew-bisubmodular function minimization

• 成果类型: Article
• 署名作者: Fujishige, Satoru; Tanigawa, Shin-ichi
• 署名单位: Kyoto University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1171-2
• 发表日期: 2018
• 页码: 87-114
• 关键词: submodular functions; polyhedra; matroids

摘要

Huber et al. (SIAM J Comput 43: 1064-1084, 2014) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain, and Huber and Krokhin (SIAM J Discrete Math 28: 1828-1837, 2014) showed the oracle tractability of minimization of skew-bisubmodular functions. Fujishige et al. (Discrete Optim 12: 1-9, 2014) also showed a min-max theorem that characterizes the skew-bisubmodular function minimization, but devising a combinatorial polynomial algorithm for skew-bisubmodular function minimization was left open. In the present paper we give first combinatorial (weakly and strongly) polynomial algorithms for skew-bisubmodular function minimization.