論文書きと査読
なんか日常的な生活に戻ったかも．
最適化ワークショップ
12月に東工大で行なわれる最適化ワークショップで講演させていただくこととなった．
チュートリアル的なもの，ということなので，最近考えている「組合せ最適化理論の三次元描像」というタイトルで組合せ最適化の理論家がどのような考え方をするのかということの私見を講演してみたい．
いまのところ予定している内容は以下の通り．
- 組合せ最適化の理論は「問題指向」のアプローチを取る．これは問題が与えられてから，それに対してどのようにアプローチをしてアルゴリズムを設計するか考える方向．それに対してメタヒューリスティクスや遺伝的アルゴリズムの研究は「アルゴリズム指向」のアプローチを取ってるのではないだろうか？つまり，まずアルゴリズムありきで，それを問題に対してどのように適用するのか考える．
- 組合せ最適化の理論は問題を分類しようとする．まず，問題がうまく解けるかどうかの分類を行なう．「うまく解ける」という概念には定義が必要で「どんな入力に対しても高速な処理で正しい答えを出力する」ことを意味し，これは形式化可能．特に高速性はチューリング機械による多項式時間計算可能性と形式化される．つまり，問題の分類は多項式時間計算可能かそうでないかで行なわれる．多項式時間計算可能であることを示すためには多項式時間アルゴリズムを設計すればよく，多項式時間アルゴリズムを持つ問題が劣モジュラ関数 (submodular function) の与える構造に支配されていると考えている．一方，多項式時間計算可能でないことを示すのでは容易ではなく，現在のところはNP困難性という傍証しか与えられていない．
- NP困難な問題であっても現実世界では何かしら解く必要はあるので，理論も黙ってはいられない．しかし，分類上うまく解けないわけなので，何かしらの妥協が必要となる．妥協が行なえる部分は3つあり「どんな入力に対しても」の部分を諦めるか，「高速な処理で」の部分を諦めるか，「正しい答えを出力する」を諦めるかのどれか，になる．
- 1つ目の妥協を「制限アプローチ」，2つ目の妥協を「厳密アプローチ」，3つ目の妥協を「近似アプローチ」と呼ぶことにする．
- 制限アプローチは入力を制限し，その制限された入力に対しては高速な処理で正しい答えを出力する．問題は制限の強さで，あまり制限しなかったら問題はNP困難なままになってしまう．逆に制限しすぎてもつまらないので，そのぎりぎりの境界を見つけたいと思うのが組合せ最適化の理論である．特にNP困難となる制限の仕方の必要十分条件を与える「二分定理」 (dichotomy theorems) を見つけることが究極の目標となる．
- 厳密アプローチはどんな入力に対しても正しい答えを出力することを維持するので，高速性を犠牲にする．つまりアルゴリズムの多項式時間性を諦めて，それよりも遅いアルゴリズムも許すこととする．問題はその遅さであり，遅い中でもできるだけ速くありたい．核となる概念はパラメータ化計算量理論 (parameterized complexity theory) と指数時間仮説 (exponential time hypothesis) である．
- 近似アプローチでは正しい答えを出力することを要求しない．問題は真の最適にどれだけ近い答えを出力できるかということである．これは近似可能性 (approximability) の議論であり，近似できることを示すためのアルゴリズム設計技法と近似できないことの傍証を与えるための計算量理論からのツールが発展してきている．後者について顕著なものはPCP定理 (PCP theorem) と一意ゲーム予想 (unique game conjecture) である．
- これら3つのアプローチは互いに直交している．つまり，入力を制限しつつ近似するとか，指数時間で近似するとか，そういうことも考えることができる．これによって組合せ最適化問題に対して「入力」「処理」「出力」を3つの軸とする三次元描像が得られる．NP困難な問題に対しては3つのアプローチの利点・欠点を互いに補いながらアタックしていかなければならない．
ご意見などありましたら，よろしくお願いします．
