最近考えていること

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

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

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