smoothed analysis

FOCS 2009 の accepted paper の一覧を眺めていて、キーワード「smoothed analysis」を含む論文が、いくつか目にとまりました。全然知らなかったので、調べてみました。wikipedia にも、まとめがあるくらい有名だったのですね。２００８年のゲーデル賞を受賞しているくらい有名だったのですね。ふむむ

smoothed analysis は、あるアルゴリズムがどれくらい「実用的か」という指標を得ようとする解析手法です。基礎とするアイディアは、worst-caseとaverage-case の補間を行うことにあります。基本的には、worst-case では指数時間なのだけど、普通に使えるよなぁというようなヒューリスティクスについて適用されるものだと思っています（きちんとした理解が必要。）

従来の解析手法では、数学と工学の間のギャップがなかなかうまく埋められず、問題視されていました。worst-case analysis で効率が良いことが示せればよいのですが、多くの場合うまくいきません。average-case analysis では、平均的な入力インスタンスってそもそも何なの？ということをきちんと押さえておく必要があります。そういうジレンマの中で提唱され評価されたのが、smoothed analysisだったんですね。まだ、あまり自分で使いこなせる自信が無いので、しっかり復習しておくようにします。

ちょっと話が変わるのですが、smoothed analysis の日本語訳はどうなるんでしょうか? amortized analysis が、「ならし解析」と訳されたりしているのをみると、ちょっと錯綜しそうですね。

アルゴリズムの解析手法に関する話題として、最近次のポストを読みました。「big-O 表記を乱用しないようにするにはこのようにすれば良いのだよ」っていう記事です。単純に log n の因子に安穏とせずに、きちんと定数項にも注意を払うべきだという記述があったり、紹介している評価基準に対する指針も記述されていて、とても興味深かったです。

それでも、今更じゃないのかなぁと固執してしまいがちな気持ちはあります。また、次の本を読んで big-O 記法を使い続けることに納得してしまっていたことも事実です。

重要なことは、問題のスケールにあわせた評価基準を正しく採用することなんだと思います。とりあえず、Smoothed analysis のまとめサイトもあって、そこで紹介されいてる論文はきちんと読んでおこうとは思いました。