著者

藤重 悟 岩田 覚

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2000, no.103, pp.53-60, 2000-11-10

---

双劣モジュラ関数最小化を行なう最初の組合せ的な多項式時間アルゴリズムを提示する.このアルゴリズムは,劣モジュラ関数最小化に関するIwata-Fleischer-Fujishigeのスケーリング法の拡張に当たる.双劣モジュラ関数はデルタマトロイドの階数関数として現れる.本論文のアルゴリズムは,デルタマトロイド多面体の分離問題に関する最初の組合せ的な多項式時間解法を与える.マトロイド多面体の場合と異なり,デルタマトロイド多面体に関するこの問題に組合せ的な強多項式アルゴリズムを与えることは,依然として未解決である.This paper presents the first combinatorial, polynomial-time algorithm for minimizing bisubmodular functions, extending the scaling algorithm for submodular function minimization due to Iwata, Fleischer, and Fujishige. A bisubmodular function arises as a rank function of a delta-matroid. The scaling algorithm naturally leads to the first combinatorial polynomial-time algorithm for testing membership in delta-matroid polyhedra. Unlike the case of matroid polyhedra, it remains open to develop a combinatorial strongly polynomial algorithm for this problem.