著者

藤重 悟 岩田 覚

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(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.

著者

岩田 覚

雑誌

情報処理

巻号頁・発行日

vol.47, no.2, pp.186, 2006-02-15

著者

岩田 覚

出版者

一般社団法人日本応用数理学会

雑誌

応用数理 (ISSN:09172270)

巻号頁・発行日

vol.20, no.2, 2010-06-25

著者

藤重 悟 岩田 覚 牧野 和久 来嶋 秀治 平井 広志

出版者

京都大学

雑誌

基盤研究(B)

巻号頁・発行日

2008

---

大規模離散最適化問題の有する劣モジュラ的な離散構造に注目し, 効率的なアルゴリズムの構築のために有効な離散構造を研究した.個別には,ネットワーク・フロー, マッチング,多品種フロー, 施設配置問題, 資源配分問題, グラフ連結度,通信網設計,待ち行列ネットワークに関わる離散構造,双対貪欲アルゴリズムに関わる離散構造(双対貪欲多面体, ゾノトープ) ,ホーン論理関数や安定マッチングの離散凸構造,などであり,個別の劣モジュラ的な離散構造の解明に基づき,それらの知見を横断的に総合する基礎理論の構築と高速アルゴリズムの開発を行った.

著者

繁野 麻衣子 山本 芳嗣 吉瀬 章子 八森 正泰 岩田 覚 後藤 順哉

出版者

筑波大学

雑誌

基盤研究(C)

巻号頁・発行日

2007

---

ネットワーク理論において横の広がりとなる基礎理論の構築と縦の広がりを作る実社会に適応したモデルの伸張を行い,基礎問題と拡張問題の両方に対して,アルゴリズム開発を行った.具体的には,修正可能性を考慮したネットワーク上の配置問題に対するアルゴリズム提案,通信ネットワークにおける耐故障性の指標開発,社会ネットワークにおけるコミュニティ抽出のハイパーグラフ上への拡張,グラフの向き付けに関する基本的性質やアルゴリズム開発などを行った.