双劣モジュラ関数最小化

• Item type: SIG Technical Reports(1)
• 公開日: 2000-11-10
• タイトル: 双劣モジュラ関数最小化
• タイトル / 言語: en
• タイトル: Bisubmodular Function Minimization
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学基礎工学研究科システム科学分野
• 著者所属: 東京大学工学系研究科計数工学専攻
• 著者所属(英): en
• 著者所属(英): Division of Systems Science Graduate School of Engineering Science Osaka University
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Engineering Graduate School of Engineering University of Tokyo
• 著者名: 藤重, 悟; 岩田, 覚
• 著者名(英): Satoru, Fujishige; Satoru, Iwata
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 双劣モジュラ関数最小化を行なう最初の組合せ的な多項式時間アルゴリズムを提示する．このアルゴリズムは，劣モジュラ関数最小化に関するIwata-Fleischer-Fujishigeのスケーリング法の拡張に当たる．双劣モジュラ関数はデルタマトロイドの階数関数として現れる．本論文のアルゴリズムは，デルタマトロイド多面体の分離問題に関する最初の組合せ的な多項式時間解法を与える．マトロイド多面体の場合と異なり，デルタマトロイド多面体に関するこの問題に組合せ的な強多項式アルゴリズムを与えることは，依然として未解決である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2000, 号 103(2000-AL-075), p. 53-60, 発行日 2000-11-10
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会