組合せ最適化問題は,有限個の要素の組合せの集合上で定義された関数の,最大値ないし最小値を求める問題である.(以下,最大値に限定する.)組合せの数は有限であるが,構成要素数に対し"組合せ数"的に増大するため,全ての組合せを調べるという素朴で確実な方法は,実用的でない.

　汎用ではないが実用的な方法に,次のような多面体的アプローチがある[3].組合せの有限個の構成要素の集合をSとしよう.Sの要素の一つの組合せは,Sの要素の各々に整数を割り当てる関数(すなわち,)で表現できる.したがって,可能な組合せの全体を,|S|-次元ユークリッド空間R^Sの全整数格子点の,ある部分集合で与えることができる.また,最大化する関数は,多くの場合,構成要素それぞれに実数を与える重み関数をもとに,組合せに対し,とxの内積^Txを割り当てるものである.このような関数は,上の線形関数になる.(この関数をと書くことにする.)このような線形関数を,組合せ全体の凸包の上で最大化すれば,その値はもとの最適化問題の解と一致する.したがって,凸包を記述する不等式系が得られれば,組合せ最適化問題は,線形計画法に帰着する.

　このアプローチには,凸包conv()を記述する不等式系が必要であるが,そのような不等式系が元の組合せ構造から,容易には得られない場合もある.いくつかのケースでは,が,組合せ構造から簡単に得られる不等式系を満たす,整数格子点の集合と一致する.このような場合の線形関数の最大化問題は,整数計画法と呼ばれ,一般に解くのは,組合せ最適化問題と同程度に難しいことが知られている.ところで,組合せ構造から導かれる不等式系の実行可能解の集合の各頂点が,整数格子点であることが保証されていれば(このような不等式系はtotally primal intgralという),それが凸包と一致することが分かる.EdmondsとGilesは不等式系のtotal dual integralityという性質を導入し,線形計画法の双対定理を使って,totally dual integralである不等式系は,totally primal integralであることを証明した[1].Total dual integralityは組合せ構造と多面体を結びつけるという,重要な不等式系の性質として知られている.

　凸包conv()を記述する不等式系を,容易に得ることができる組合せ構造の一つに,マトロイドがある.マトロイドの場合,ランク関数と呼ばれる{0,1}^S(Sの部分集合全体)で定義される関数をもとに作られる不等式系

　がtotally dual integralであり,したがって,凸包を記述する.この関数の満たす劣モジュラ性

　をもとにしたマトロイドの拡張である,ポリマトロイド,劣モジュラシステム等は,マッチング,ネットワーク流,その他の構造を同時に扱える枠組となっている.

　マトロイドや,その拡張である,デルタマトロイド等の組合せ構造上の,線形関数の最適化は、多面体アプローチ以外にも,欲張り算法と総称される非常に単純で効率のよいアルゴリズムで,組合せ的に解けることが知られている.そればかりでなく,マトロイドやデルタマトロイドは,"最適化問題が欲張り算法で解ける,あるクラスの組合せ構造"として定義することもできる.また,劣モジュラ関数で作られる,不等式系(1)の実行可能解集合上での線形関数の最大化も,ある種の欲張り算法で解決できることが知られている.これは,欲張り算法の有効性を保証する,1対1交換可能性,およびその言い替えである関数の劣モジュラ性が,既知のマトロイド的構造に共通して存在するからである.なお,ここでいう1対1交換可能性とは,

　二つの可能な組合せx,y∈について,xの任意の構成要素u∈Sの数x(u)を,yのそれに1だけ近づけても,ある別の構成要素∈Sの数x()も,同時にyの方に1だけ近づけて,可能な組合せにすることができる.

　という性質のことである.

　この論文の目的は,劣モジュラ関数およびデルタマトロイドの1対1交換可能性を仮定しない拡張と,それに関連する最適化間題を解くアルゴリズムについて論じることである.

　まず,劣モジュラ関数の一般化が紹介される.マトロイドの1対1交換可能性は,劣モジュラ関数では,二つの面で反映される.一つは,不等式系(1)の各不等式の定める半空間が,01-ベクトルを法線とすることで,これは関数の定義域が{0,1}^Sであることの帰結である.もう一つは,これらの半空間の交わり方が(2)から導かれる,良い交わり方をしているということである.本論文では,012-ベクトルで定義される関数の、良い交わり方をもたらす関数の性質

　を提示している.(ここで,は,Xの特徴ベクトルを表す.)(3)は,ある種の増幅器付きネットワークから導かれる性質を,抽象化したものであることが明らかにされる.劣モジュラ関数の整数格子点への拡張としては,劣モジュラ関数のLovasz拡張[2]や,L-凸関数[4]が知られているが,(3)は,それらとは異なる拡張を与える性質である.

　さらに,012-ベクトルの間にある半順序を定義し,"良い交わり方"を,この半順序の最大鎖を使って記述している.逆に,この"交わり方"をする不等式系を定めるならば,012-ベクトルで定義される関数は,(3)を満たすことも証明される.

　その後,最大鎖による特徴付けをもとに,この関数の定める不等式系上での線形計画法を,双対問題の側から解くアルゴリズムを提案する.このアルゴリズムを通じて,この関数から作られる不等式系がtotally dual integralであることが明らかにされる.

　最後に,"分離定理"と呼ばれる,劣モジュラ関数やL-凸関数について知られている定理が,このような関数に対しても成立することを示す.この分離定理により,増幅器付きネットワークの可能な出力の集合が作る多面体が,{0,1,2}^Sで定義された,(3)を満たす関数により,記述できることも示される.

　続いて,マトロイド,デルタマトロイドを含むクラスである,2対2交換可能性が成立する組合せ構造の,最適化問題が論じられる.

　欲張り算法は,に属する各組合せの間に,重み関数から導かれる,ある辞書的順序の下で,最初になる組合せを解とするアルゴリズムということができる.ここで提案される弱欲張り算法は,少しアレンジした順序の下で,最初になる組合せを求めるアルゴリズムである.この順序は,辞書的順序とは異なり,全順序にならないため,複数の最適解の候補を扱う必要があるが,この解の候補間の辞書的順序を用いることにより計算のオーダーを落せることを示す.

　さらに,このアルゴリズムが適用できる,2対2交換可能性を満たす組合せ構造の,ランク関数と,禁止マイナーによる特徴付けが,それぞれ述べられる.

　集合関数の劣モジュラー性は、組み合わせ最適化と多面体的組み合わせ論の分野で重要な役割を果たす概念のひとつである。論文提出者は、本論文においてこれが適当な条件の下で{0,1,2}を座標値にもつn次元格子点上の関数に拡張できることを示し、これにより劣モジュラー関数においてこれまで成立していた種々の性質と定理がより一般的な枠組みで成立することを明らかにした。

　多面体的組み合わせ論は、1960年代のD.R.Fulkersonによるネットワークフローの研究とJ.Ed-mondsによるポリマトロイドの導入、マトロイド交叉定理の確立に端緒を発する。多面体的組み合わせ論では、問題の制約条件が与える多面体でその各頂点が整数点であることをまず示し、これと線形計画法の双対定理を合わせることにより組み合わせ論的な性質を導くという証明の道筋をたどる。

　この観点からみると、ネットワークフローの持つ良い組み合わせ論的性質は、グラフの点-枝接続行列が常にtotally unimodularになり、これを制約行列に持つ線形不等式系に整数最適解を持つことが保証できるという事実に帰着できる。また、マトロイド交叉定理も、ある特定の性質を満たす集合族の表現行列がtotally unimodularになるという事実に帰着できる。このように、制約行列もしくはそれが定める多面体が整数性を持つことを保証できるところから、これらの離散的なシステムの組み合わせ論的な良い性質が生まれてくる。

　上述の場合のように、これまでは制約行列の要素は基本的に0,1の値に限られていたが、論文提出者はこれを0,1,2の場合にまで拡張することを考え、どのような条件の下で多面体の整数性が成立し、どのような前提のもとで欲張りアルゴリズム(greedy algorithm)がうまく働くのかを詳しく研究した。そして、{0,1}ⁿ上の通常の劣モジュラー関数が、greedy-typeと名付けられた{0,1,2}ⁿ上の関数へ、もとの良い性質を保持したまま拡張できることを示した。

　この一般化された劣モジュラー関数とも呼ぶべきgreedy-type関数に対して、論文提出者は次のような結果が成立することを示した。

　まず、台集合S上の劣モジュラー関数において、Sの部分集合の任意の極大鎖$113165f10.gif$をとれば、その差分の列$113165f11.gif$がが与える多面体のある頂点の座標に一致し、かつ頂点はすべてそのような形で表されるという事実はよく知られている。ここで、0,1,2を係数とする一次制約式からできる多面体においても、劣モジュラー性を適当に拡張した条件の下で各頂点とそこに接する面の全体との間に同様にきれいな関係が成り立つことを論文提出者は明らかにした。つまり、座標値が0,1,2のn次元格子点の集合上にある半順序関係を巧妙に導入することにより、greedy-type関数の定める多面体の各頂点ではそこに隣接する面の全体がこの半順序集合の極大鎖に対応し、かつその逆も成立することを明らかにした。

　次に、この頂点一面の接続関係の詳しい解析結果を利用して、greedy-type関数の定める多面体上の線形重み最適化問題を解くための主双対型の欲張りアルゴリズムを構成し、かつこのアルゴリズムが常に最適解を与えることを証明した。これは、グラフの木、マトロイドの基に対するKruscalのアルゴリズム、デルタ・マトロイド上でのA.Bouchetの一般化欲張りアルゴリズムなどの既存の結果の拡張になっている。

　第三の結果として、greedy-type関数が与える不等式系がtotally dual integralであることを示した。これにより、greedy-type関数が整数値であれば、それが定める多面体が整数値になることが保証される。

　実数値関数の最適化の理論の中で凸関数は特別に大事な役割を果たすが、劣モジュラー関数が離散的な世界での凸関数の概念に当たることは広く認められているところであり、また凸関数と凹関数のあいだのよく知られた分離定理に対応して、劣モジュラー関数と優モジュラー関数との間に離散的な分離定理が成立することも知られている。論文提出者は、greedy-type関数においてもこの分離定理が拡張された形で成立することを示した。このことは、本論文のgreedy-type関数が劣モジュラー関数の自然な拡張のひとつであることを示唆している。

　また、これらとは別に、デルタ・マトロイドにおける1対1型の交換公理を同時に2元を入れ替える2対2型の交換公理に置き換えたものをペア・デルタマトロイドと名付け、考察している。ここでは、一般的な欲張りアルゴリズムを素朴に適用しただけではうまくいかないが、計算の手間が少し増えることを犠牲にすれば、欲張りアルゴリズムを変形したアルゴリズムを使って最適解が得られることを示している。

　以上要するに、論文提出者は、組み合わせ最適化理論の核であるマトロイドと劣モジュラー関数の理論において、きわめて革新的な概念を導入し、これにより既存の諸結果がひろく拡張された形で成立することを明らかにした。これらの諸結果は、マトロイド理論を専門にする人たちのみならず、離散的な数学及びアルゴリズムの理論の研究者から広く評価される研究である。また、本論文の一部はすでに国際シンポジウムで発表され、学術論文としても刊行されている。

　よって本論文は博士(学術)の学位請求論文として合格として認められる。