数理最適化の分野には、数多くのNP-困難な問題が存在する。これらの問題に対して多項式時間解法が存在しない事を、殆んどの研究者が信じている。この事実へ対処方法として、二つ方法がある。一つは古典的な方法で、発見的解法を用いるアプローチである。つまり、問題に対して、理論的な保証は無いものの、経験的もしくは実験的に高速に解け、かつ最適解に近いと思われる解を出力する解法を用いるものである。工学的応用においては、この手法は非常に実用的であり、実務においては多くの場合充分な性能を備えている。しかしながら発見的な解法は、"実用に使える解"を制限時間内に"必ず"答える事は保証できない。この事に対処する為に、近年になって近似解法の構築というアプローチが研究されるようになってきた。近似解法とは、保証された精度を持つ許容解を必ず答えてくれる解法である。計算時間がデータ入力サイズの多項式でおさえられる近似解法を特に多項式時間近似解法と呼ぶ。

　本論文では、近似解法の研究において大きなブレークスルーと目されている、1995年に発表されたGoemansとWilliamsonの解法を元にして、新たな解法を提案する。取り扱う問題は、最大有向カット問題(maximum directed cut problem;MAX DICUT)、及び、最大2-充足可能性問題(maximum 2-satisfiability problem;MAX 2-SAT)である。これらの問題に対して知られていた最も良い近似解法の近似比は、それぞれ1/4、3/4であったのに対し、GoemansとWilliamsonは、近似比0.79607、0.87856を持つ解法を提案した。この結果を受けて、FeigeとGoemansは新たな手法を導入する事によって解法を改良し、近似比を0.931と0.857に改善した。その後、Zwickによりさらに僅かに改善され、0.931091と0.859643という近似比を持つ解法が提案された。これらの近似比は数値計算によって算出されており、解析的には求められていない事に注意されたい。

　本研究では近似比を改良する新たな手法を提案している。これにより近似比はさらに改善され、MAX DICUTとMAX 2-SATに対し、0.935と0.863という近似比を持つ解法が構築できた。

　最新の結果では、Lewin、Livnat、Zwickにより近似比0.940と0.874が達成されている。この結果は、FeigeとGoemansの手法と我々の手法を組み合わせる事によって達成されている。

　GoemansとWilliamsonの解法では、問題を整数計画問題として定式化している。ただし、各変数は{-1、1}の値のみを取るものである。彼らの解法は、この整数計画問題を半正定値計画(semidefinite programming;SDP)問題に緩和している。SDPは多項式時間で解ける事が知られているので、多項式時間で緩和問題の最適解が得られる。この最適解を元に、高次元の超球面上に分布したベクトルの組を求める、次に、超球面上に一様な確率でベクトルを一つ定め、緩和問題の最適解から得られたベクトルとの内積の符号により、元の整数計画問題の変数値を定める。この一連の操作により得られる解による目的関数値の期待値が、最適値の0.79607、0.87856倍以上である事が示されたのである。

　本論文で示す解法では、高次元の超球面上に分布したベクトルの組において、特別な次元が一つだけ存在する事に着目する。超球面上に一様な確率でベクトルを一つ定めるかわりに、特別な次元の方向には適当な分布密度を持ち、その他の次元の方向では一様であるような確率分布密度に従ってベクトルを定める。これを"歪んだ分布密度関数に基づく超平面分離法(hyperplane separation technique with skewed distribution function)"と呼んでいる。この解法は、一見単純に思えるが、良い分布密度関数を求めるにあたって、解決すべき自明でない問題点が存在する。より詳しく述べるならば、ある分布密度関数を用いた際の近似比が、発生させるベクトルの次元に密接に依存している。そこで本論文では、2次元球面上での分布密度関数とn次元球面上での分布密度関数との間の関係を示し、さらに、2次元球面上で定義される分布密度関数の特殊なクラスを提案する。このクラスに属する関数は、一つ定めると、それに対応して任意の次元において同じ近似比を達成する分布密度関数を求められるという性質を持っている。さらに、2次元球面上での提案された関数クラスの中から良い近似比を達成する関数を選ぶ方法を述べている。その結果、上で述べた通り、近似比がMAX DICUT、MAX 2-SATに対し、それぞれ0.935と0.863となる分布関数を求める事ができた。

　また、提案した解法は確率的解法(randomized algorithm)であるが、MahajanとRameshによるGoemansとWilliamsonの解法に対する脱ランダム化(derandomization)手法を援用する事により、同様に脱ランダム化を行なって、決定的解法(deterministic algorithm)も示した。さらに、この手法で得られる決定的解法の近似比は、分布の歪みに本質的に依存していない事実が明らかになった。そのため、本研究は解法の提案ではなく、新しい解析手法の提案としても捉える事が可能になった。

　組合せ最適化の分野においては、ネットワークフローのような良い構造が離散凸性として認識される一方、巡回セールスマン問題に代表されるNP困難問題への挑戦が続けられており、応用からの強い要請を受ける形で、メタヒューリスティックと総称される一群のアプローチや理論的保証を伴った近似解法が開発されている。本論文では、NP困難な問題の中でも中心的な位置を占める最大有向カット問題(maximum directed cut problem;MAX DICUT)、及び、最大2-充足可能性問題(maximum 2-satisfiability problem;MAX 2-SAT)に対し、新たな近似解法の提案を行う。本研究で提案する解法は、近似解法の研究における大きなブレークスルーであるGoemansとWilliamsonの解法(1995年)を改良し、それぞれの問題に対して近似比0.863と0.935を達成している(この近似比は解法提案時点における世界記録である)。本論文はこれらの手法とその理論解析について論ずるものであり、6章からなる。

　第1章は「序論」であり、研究の背景や関連する既存の概念の紹介を行うとともに、本論文の目的を述べている。

　第2章は「記法と問題の定義」である。特に本研究で取り扱うMAX DICUTとMAX 2-SAT及びそれらに関連する問題についてその相互関係を整理している。

　第3章は「先行研究」であり、MAX DICUTとMAX 2-SATの近似解法の先行研究についてまとめている。特に、GoemansとWilliamsonの解法における半正定値計画緩和と超平面分離法による許容解導出法について詳細に記述している。GoemansとWilliamsonの解法の近似比は0.79607と0.87856であるが、その後、FeigeとGoemansは「回転」と称する技法を導入して近似比を0.859と0.931に改善した。さらに、Zwickはその技法を改良して0.859643と00.931091という近似比を持つ解法を提案した。上記の先行研究はすべて確率的解法であるが、これらの解法から確率的な手続きを取り除き決定的な解法を構築する「脱ランダム化」と呼ばれる手法がMahajanとRameshによって提案されている。第3章では、これについても記述している。本章の最後に、多項式時間近似解法の近似比の理論的上界について簡単にまとめてある。

　第4章では、新たな近似解法の提案を行っている。本論文で提案する解法では、GoemansとWilliamsonの解法と同様に、問題を整数計画問題として定式化し、これを半正定値計画問題に緩和し、その解をもとに高次元の超球面上に分布したベクトルの組を求める。最後に、超球面上に「適当な」確率でベクトルを発生させ、別に定めたベクトルとの内積の符号に基づいて元問題の近似解を構成する。この近似解の期待値が、MAX DICUTとMAX 2-SATに対してそれぞれ、最適値の0.863と0.935倍以上であるというのが本論文の結果である。

　本論文以前の解法が、超球面上に一様な確率でベクトルを一つ定めているのに対して、本論文では、高次元の超球面上の分布において特別な方向が一つだけ存在する事に着目し、その特別な方向には歪んだ分布密度を持ち、その他の方向では一様分布に従うベクトルを用いる。これを「歪んだ分布密度関数に基づく超平面分離法」と呼んでいる。このアイデアに従って解法を具体的に設計するには、良い近似値を与えるような歪んだ分布密度を定める必要がある。本論文では、高次元球面上の分布密度とその2次元球面上の周辺分布との関係を解析し、近似解法の設計に有用な2次元球面上の分布密度のサブクラスを提示している。このサブクラスに属する関数は、それに対応して任意の次元において同じ近似比を達成する分布密度を求められるという性質をもつので、2次元球面上の分布密度のサブクラスの中から良い近似比を達成する関数を選べば良いことになる。この解法は確率的解法であるが、本論文ではさらに、MahajanとRameshによる脱ランダム化手法が適用できる事を示して、決定的(非確率的)解法をも与えている。

　第5章では、近似比率を計算するための数値計算手法を述べている。加えて、より良い近似比率を実現する分布を探索するための指針についても議論している。

　第6章は「まとめ」であり、本研究によって得られた知見と、今後の研究の展開の可能性について述べている。

　本研究は、組合せ最適化の分野における最先端の研究であり、世界中で数多くの研究者が凌ぎを削る中で、新たな手法を考案することによって、達成可能な近似比の下界値を更新したものである。数理的な考察に基づいて工学的に有効な手法を開発したものであり、数理工学の分野に大きく寄与する研究として、高く評価できる。

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