オンラインアルゴリズムとストリームアルゴリズム

オンラインアルゴリズムとストリームアルゴリズム (アルゴリズム・サイエンスシリーズ―数理技法編)

ようやく目にすることができました．
今年度は既にいろんなところに行き過ぎで，書籍すら買う余裕がなさそうなので未購入だけど，何とかして読みたいです．

ぱらぱら立ち読みしたところ，本論と関係ないあとがきやまえがきや補足のところが個人的には好きです．
まぁ，本論はぱらぱら読んだだけでは分からないので仕方ないですが．

ちなみに，オンラインアルゴリズムとは一言でいうなら「分からない未来に対するアルゴリズム」で，それを統計的に扱おうとすると予測理論になるのですが，そうではない形で理論展開するところが面白いわけです．
一方，ストリームアルゴリズムは一言でいうなら「過去を(少ししか)記憶できないアルゴリズム」で，やってくるデータをどんどん処理して欲しい情報を得ることを目的とします．
どちらもアクティブな研究分野です．

Online Computation and Competitive Analysis

Online Computation Compet Analysis

オンラインアルゴリズムの教科書として定番の本です．
今オンラインアルゴリズムを研究してる人はみんなこの本で勉強しました．
私もチューリッヒにいたときオンラインアルゴリズムの授業をとって，この本で勉強しましたが，すっかり忘れてしまってますね．いけません．オンラインアルゴリズムが出てくる論文を1つ書いてるのに．

最近考えていること

こんなこと書いちゃっていいんだろうか．まぁ誰にも分からないからいいか，と．もし分かってしまったという方はご一報下さい．一緒に仕事しましょう．

• 情報可視化関係．棒グラフ問題はNP困難性を証明してもらったので近似アルゴリズムを作る必要あり．木のマッチングの方は厳密アルゴリズムを私が作ることになっている．
• 幾何関係．最近またTSP (巡回セールスマン問題) が気になっている．パラメータ化計算量理論から眺めたい．そういえば，MaxTSPもちゃんとやらないといけなかった．2年ぐらい前のことだから早くやらないと忘れてしまう．半年前ぐらいに書き始めたらどうも面倒くさくなってしまって宙ぶらりんになっている．
• ゲーム理論関係．シャプレイ値をとりあえずなんとかしよう．
• 線形計画法関係．やりたいと常に思ってるのに，全然まとまった時間がとれない．
• グラフ関係．マッチングの数え上げをずっと考えてるけど，全然わからない．糸口なし．糸口ないので具体的な問題を書いてしまうと，単位区間グラフの完全マッチングの数え上げを多項式時間でやりたい話と，二部グラフの大きさkのマッチングの数え上げがパラメータ化計算量理論の意味で難しいこと (これはFlum-Groheが予想してる) を示すという話．

その他，学生に出しているテーマがあるけど，それはここに書いちゃまずいから書けない．