著者

牧野 和久 高畑 貴志 藤重 悟

雑誌

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

巻号頁・発行日

vol.2001, no.115(2001-AL-081), pp.27-34, 2001-11-27

---

本論文では,△-正則2 部グラフに対する完全マッチング問題を考察する.ただし,グラフG は,n 節点,m 枝,すなわち,1/2 n △=m とする.我々は,まず,Gabow の方法に基づく新しい単純なO(m log n )アルゴリズムを与える.次に,Cole とHopcroft が提案した正則2 部グラフに対する辺疎化手法を取り入れることにより,そのアルゴリズムをO(m +n log n log △)に改善する.我々のアルゴリズムは,動的木やスプレイ木などの高度なデータ構造を必要としない.

著者

藤重 悟 岩田 覚

出版者

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

雑誌

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

著者

藤重 悟

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.21, no.2, pp.189-204, 1978

被引用文献数

1 30

---

G(V、A^*;V_1、V_2)を、点集合V、枝集合A^*、および、"入口"V_1(⊆V)、"出口"V_2(⊆7)をもつグラフとする。簡単のためV_1∩V_2:φとしておく。グラフGの各枝αには、その容量c(α)と単位流量当りの費用γ(a)とが付与されているとする。さらに、人ロV_1と出口V_2上に、それぞれ、ホリマトロイドP_1(V_1、ρ_1)、P_2(V_2、ρ_2)が定義されているとする。以上の諸量の定義されたグラフをネットワークNと呼ぶことにする。N上の"独立流れ"とは、各枝の容量条件を満たす入口V_1から出口V_2へのG上の流れであり、かつ、V_1への流入ベクトルがP_1の、V_2からの流出ベクトルがP_2の、それぞれ、独立ベクトルであるようなものである。ただし、V_1への流入ベクトルとは、各v^εV_1にvへの流入量を対応づけるベクトルである(流出ベクトルについても同様)。"独立流れ問題"とは、(1)N上の最大独立流れ(すなわち、V_1からV_2への最大流量をもつN上の独立流れ)を見出す問題、および、(2)N上の最大独立流れのうちで費用が最小であるものを見出す問題、のことである。本論文では、与えられた独立流れに関連して定義される補助ネットワークを用いて独立流れ問題を解く算法を提示する。プライマル・デュアルな形の算法は概略つぎのようである。N上のある独立流れから出発して、補助ネットワーク上の最短路を見出し、それに基づいて流れを変更し、流量が増加した新たな独立流れ(問題(2)の場合は同じ流量をもつ独立流れのうちで最小費用の独立流れ)を得る。さらに、得られた独立流れに関連する補助ネットワ-クを構成し、以上の手続きを繰返す。問題(2)に対しては、プライマルな形の算法も提示してある。これらの算法を導出する過程において、最大独立流れや最小費用の最大独立流れを特徴づけるいくつかの命題が、構成的に証明される。複数個の(ポリ)マトロイドが関係するような、今までに提起されている問題のうちの多くは、独立流れ問題として"自然な形で定式化される。ネットワーク流れ問題としての定式化が多くの組合せ的問題に対して有効であったのと同様に、独立流れ問題としての定式化が(ポリ)マトロイド的な組合せ的問題に対して有効である。なお、パラメタc(a)(a^εA*)、ρi(A)(A⊆V i;i=1、2)が可約な場合、本論文で提示した算法は有限回の操作の後に終了し解を与える。一般の独立流れ問題に対し本論文で提示した算法が有限回の操作の後に終了するか否かの問題、有限回で終了するとすればその手間の評価の問題、などは今後に残された課題である。

著者

藤重 悟 牧野 和久 高畑 貴志 柏原 賢二

出版者

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

雑誌

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

巻号頁・発行日

vol.2001, no.7, pp.51-58, 2001-01-19

---

各辺ベクトルの台の大きさが2以下である多面体のクラスについて考える.このような凸多面体を複基多面体と呼び,頂点をもつ任意の多面体P⊆R^Vについて,次の3つが等価であることを示す.(1) Pが複基多面体である.(2) 台Vの法線ベクトルをもつPの各面は,ある基多面体の反転および軸方向のスケーリングによって得られる.(3) Pの支持関数は,R^Vの各象限上の劣モジュラ関数である.We consider a class of pointed convex polyhedra in R^V whose edge vectors have the support of size at most 2. We call such a convex polyhedron a polybasic polyhedron and show that for a pointed polyhedron P ⊆ R^V the following three statements are equivalent: (1) P is a polybasic polyhedron. (2) Each face of P with a normal vector of the full support V is obtained from a base polyhedron by a reflection and scalings along axes. (3) The support function of P is a submodular function on each orthant of R^V.

著者

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

出版者

京都大学

雑誌

基盤研究(B)

巻号頁・発行日

2008

---

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