日記
2005/1/31
実は今、本を書いています。
書いている、と言っても1つの章の半分を担当しているだけですけど。
僕の担当した章はもう出来ています。去年の冬頃に。
で、終わってないのは何かというと、その本のproofreadingです。
全然終わりません…。
一応読んでるには読んでるんですけどね。
ただ、「多項式時間で解けない問題はNP-困難であるという」とか書いてある部分があって、指摘するには指摘しなくちゃいけないんですけど、
こういう初歩的な間違いが1つでもあると、その章全体の信頼度が下がってしまうのでよくないですね。
2005/1/27
STOC 2005の受理論文一覧が出ていたので眺めてました。
やはり計算量理論の方では、ランダム性や符号、暗号に関する話題が目につきます。
無向グラフのst連結性の領域計算量の論文も2つちゃんと受理されています。
グラフ関連だと、Thorupの動的アルゴリズムに関する論文とか、その他にはproperty testingに関する論文や近似アルゴリズムに関する論文が目をひきます。
あとは、ゲーム理論に関連するアルゴリズムもいくつか見られます。
もっと気になるのは、低歪み埋め込み (low-distortion embedding) に関する論文ですね。
これはここ最近急激に進展している分野で、特にアルゴリズムに関する技法や結果が沢山出て来ています。
その応用には、sparsest cutの近似、minimum bandwidthの近似があり、近似アルゴリズムの分野とも密接に関連しています。
その他ですが、Basuの半代数的集合に対するアルゴリズムの論文がいくつか受理されてますね。
ここら辺りも面白そうな話題ですね。
2005/1/25
博士論文発表会。
無事に終了しました。
ということで、パン、ひたすら切りまくりました。
チーズ、あまりすぎです。ワインもちょっと余ってます。
全然、発表会の感想になってないですね。
スライド準備とかあまりちゃんと出来てなくて、最近は発表原稿とかも作らずにアドリブで話すので、うまく出来るかどうか心配でしたけど、なんとかできたと思います。
質問への回答も何とかやりこなしました。
ちょっと緊張してたみたいでしたけど、まぁ、終わってよかったです。
2005/1/24
いよいよ明日、博士論文の発表会です。
発表そのものよりも、その後のアペロ (小さなワインパーティー) の準備の方が忙しいです。
ここら辺では、この手のパーティーは自分で用意するのが文化のようです。
ということで、ワインなどの飲み物やクラッカー、チーズ、サラミとプチトマト、マスカット、その他おつまみを買ってきて大体準備できました。
明日は、パンを4本ぐらい買ってきて、ひたすら切ります。
しかし、発表会は30分なんですね。
30分なんですが、スライド枚数が80枚…。
誰が考えても収まりそうにないですが、これが収まるんです。
びっくりします。
2005/1/20
3日前からWeismantelが福田先生のところにきています。
2日前に講演があったので聞きにいきました。
内容は多項式整数計画法のアルゴリズムです。
これは面白いですね。Barvinok-Woodsのアルゴリズムとかを中で使うわけですけど、そこら辺りももう整数計画の分野では標準になってる感じがしますね。
もう一つ得た情報として、WeismantelがBertsimasと書いた新しい本のことがあります。
今年出版されるようで「Optimization over Integers」という本だそうです。
個人的にはとても読みたい本です。
2005/1/17
あけましておめでとうございます。1ヶ月ぐらい更新してませんでした。
トロピカル階数の計算がNP困難という論文がarXiv.orgに出てます。
この問題は1年ぐらい前から目をつけていて、去年のGWOPにも投稿した問題なのですが、ようやく解決したということで、ほっとしました。
01行列の場合でもNP困難のようです。
ちなみにnxn行列のトロピカル階数とは、そのnxn行列を頂点数n+nの完全2部グラフの辺の上のコストだと思ったときに、そのグラフの頂点数k+kの完全2部グラフで、その上の最小コスト完全マッチングが唯一になるものが存在するようなkの最大値、のことです。
2004年12月の日記
過去の日記のリスト
[トップ]
okamotoy@uec.ac.jp
Last modified:Mon Jan 31 22:32:41 2005