| テーマ | 「線形計画法を利用した近似アルゴリズム」 |
| 内容 | MAX-SAT問題に対していろいろなものが提案されている数種類の近似アル ゴリズムを組み合わせて１つの近似アルゴリズムを作り、そのパフォーマンスを線 形計画法を利用して解析すること |
| テーマ | 「半定値計画法を用いた MAX CUT 問題の近似解法に関する研究」 |
| 内容 |
計算機科学の分野において，多項式時間で解けないようなＮＰ困難問題を解
く際に，この問題を多項式時間で解ける別の問題に緩和して近似解を求めると
いった方法があります．これを一般に近似解法といい，それを解く手順を近似
アルゴリズムと呼びます．緩和した別の問題で得られた解と，もとの問題の解
を比較したときに，その誤差が無視できるとみなせるくらい小さなものであっ
たとき，もとの問題を解く操作をこの別の解法で代用させても差し支えないと
言えます． こういったＮＰ困難問題の近似解法に対しての理論的枠組について実 際に計算機実験を通して調査・研究しています． |
| テーマ | 「グラフの最小Ratio-Cutの近似アルゴリズムに関する研究」 |
| 内容 |
Ratio-Cutとは部分グラフの大きさのバランス及びカットする辺の
最小化の両方を考慮に入れたグラフの分割のことである。 グラフのスペクトルを求め、それに基づきグラフの最小Ratio-Cut を行なう。 スペクトルとはラプラシアンという行列の２番目に小さい固有値 に対応する固有ベクトルから得られる。 Ratio-Cutの下界（lower bound）はラプラシアンの２番目に小さい 固有値で与えられる。 |
| テーマ | 「デマンドバス運行管理問題」 |
| 内容 | デマンドバスとは、ある定められた地域内における乗降車依頼に対し、車両 基地に配備されている小型バスによる相乗り方式のサービスを行なうシステム をいう。デマンドバス運行管理問題とは、乗降車依頼に対する車両の割り当て とバスの巡回経路とを決める問題である。 本研究では、離散最適化問題の一種である Pickup and Delivery 問題や Dial a Ride 問題をベースとしてデマンドバス特有の条件を取り入れモデル化、 定式化を行なう。そのモデルのもとで最適な巡回経路および運行スケジュール を求める手法について考察する。 |
| テーマ | 「MAX SAT における近似アルゴリズムの実験的評価」 |
| 内容 | 最大充足化問題（MAX SAT）とは，重み付きの節の集合が与えられたときに， 充足する節の重みの和を最大にする割当を求める問題です． MAX SAT 問題は NP 困難であり，線形時間で解くアルゴリズムは発見されていません． そのため MAX SAT を解くさまざまな近似アルゴリズムが提案されています． しかし，これらのアルゴリズムはこれまで実際問題に適用したとき， 実用になるかどうかはまだ分かっていません． そこで，実際に計算機上でこれらのアルゴリズムを実現し， 計算時間や領域計算量などを評価します． |
| テーマ | 「MAXSATの発見的アルゴリズムに関する研究」 |
| 内容 | MAXSATとは正の重みの付いたクローズの集合を与えられたときに、充足するクローズの重みの和を最大にする割り当てを求める問題です。この問題はNP困難であり多項式時間で解く事が出来ないことがわかっており、そのためMAXSATを解く様々な近似アルゴリズムが提案されています。そこでこの研究では発見的アルゴリズムを用いた解法を計算機上に実現し、それを評価するのが目的です。 |