OR 学会参加！アルゴリズムの効率性の問題

今週木・金と、OR 学会 (開催地: 筑波大学) に行ってきました。

今回は 3回に分けて、面白かった発表の感想を書いてみたいと思います。

まずは 1つめの発表（研究賞受賞記念講演）です。

『組合せ最適化におけるアルゴリズムの理論的な効率性

小林 佑輔 さん』

です。

この発表では、タイトル通り、アルゴリズムをどれだけ効率化するかと言う視点での研究が発表されました。

元々の問題は、下記の 3 段階に分かれます：

[1] 現実の問題 (通信、物流、都市計画など) にアルゴリズムを適用して解決する.

[2] 効率的なアルゴリズム (基本は多項式時間アルゴリズム) を考える.

[3] [2] のための基礎研究、基礎科学.

上記 [1] 〜 [3] の問題のうち、小林さんの研究は、[2] の部分に該当します。

小林さんの研究は、『離散最適化問題』と言って、ネットワークやグラフなどの離散的な構造において、なんらかの指標を最大化・最小化する問題を扱っています。

そのために、計算時間が入力サイズの多項式時間で抑えられるアルゴリズムをいかに作るか、という点に重点を置いて研究をされているそうです。

今回の小林さんの発表をわかりやすく噛み砕いて説明すると、例えば現実世界での通信の問題で、ノードとエッジというものを考えるケースがあるじゃないですか。

そのノードを点、エッジを辺として、2次元の多面体の図形 P を作ります。そこで、通信の問題を 『2次元の多面体 P を解析する』という問題に帰着させて考えることができる、という点が基本となるんです。

しかし、実際に 2次元の多面体 P をそのまま解析するのは難しいので、P に頂点や辺を付け足して、3次元の多面体 P’ を作ります。そこで、3次元の世界では自由度が増えますから、『3次元の多面体 P’ を解析する』という問題を考えれば、P’ について何らかの答えをうまく導き出すことができるかも知れません。

そこで仮に、 3次元の多面体 P’ で問題が解決されたら、それを元の 2次元に射影して P に関する問題に立ち戻れます。そこで問題 P’ の答えを P にうまく射影できれば、それは元の問題 P に対する答え（つまり、多項式時間時間アルゴリズム）となっている、というのが小林さんの研究の最も重要な点であったと青いわしは考えております。

これは数直線上での定積分の計算が困難な時、複素平面における積分を経由して計算することに似ているなあ、と思いました。

さて、上記では通信の問題と言いましたが、この解析方法は通信だけではなく、物流や都市計画（交通網の整理）や、はたまた軍事にも適用できると思います。

小林さんの研究は幅広い応用を持つと思うのですが、小林さんご自身が発表の中でおっしゃっていた通り、この研究をどれだけ現実の問題に適用できるかは、今後の課題の一つだそうです。

OR （オペレーションズ・リサーチ）の世界では、どうやって問題を解決するか、に重点を置くため、あまり数学的な内容に踏み込んだ発表ではなかったのですが、数学的な立場から見ると、面白いアイディアの宝庫のような気がしました。