また自転車を買ってしまった。 まだ2台目だから場所は大丈夫だけど、 これ以上買うと置き場所がヤバイな。あと、シャワーを浴びているときに、 Amazon.comから何かが届いてた。 たぶんKindle

受理された論文のレビューが送られてきた。 前回落とされた時のレビューに比べると、 査読者がしっかり読んでくれていることがわかるようなレビューだった。

そしてVazirani本。 わかんなかったところが、わかった。 よく考えると、当たり前のことが書いてあるので、 詳しい説明をしなかったのだと思うが、私のような初学者の為に、 もう少しわかりやすかったらよかった。 この部分を過ぎたら、サックリ読破。 続い…

やっぱりVazirani本。 ５章のk-center問題を勉強中。 詳細はMetric k-center - Wikipedia。 ちなみに、distanceがmerticでないとすると、P=NPでない限り、 計算可能関数f(n)において、近似率f(n)以内を達成できないことが知られている。ある証明がよくわかん…

初Acceptキタッ!!

引き続きVazirani本４章。 Multiway cutとMinimum k-cutの近似アルゴリズムについて。 Multiway cutはk個のterminal集合が与えられたときに、 あるcutを取り除くと、各terminalが別々の連結成分に属するような、 最小重みのcutを求める問題。k>=3でNP困難で…

引き続きVazirani本で勉強。 ３章まで完了。あんまり内容について記述するのはまずいのかな？ Metric TSPの2-近似とそれを1.5-近似に改善するところが面白かった。 2-近似はシンプルで良いのだが、2-近似の何が悪いのかをしっかり分析して、 それをうまく改…

今日はVaziraniの近似アルゴリズムの本の１章を読んだ。 頂点被覆問題は、グラフの極大マッチングを求めて、 両端点をカバーすると、2-近似アルゴリズムになる。 近似アルゴリズムの知識は余り無いので、これを機に勉強する。 今日は２章まで読んで寝よう。

ヨセフス問題のk=2の特殊な場合。 TLEで放置してたんだけど、wikipedia見たら答えが書いてあった。 n人で一人飛ばして処刑していくとき(つまりk=2)、 nは二進法でb_0b_1b_2b_3...b_kであるとき、解はb_1b_2b_3...b_kb_0になるらしい

５日連続で疲れたけど、内容も充実していたのでよかった。 まぁ、まだレポートが残ってるけど。 明日はオープンキャンパス。

http://math.mit.edu/~goemans/teaching.html http://homepages.cwi.nl/~lex/ http://www.cs.illinois.edu/homes/chekuri/

とりあえず進路の確保はできたので、あとは研究するのみ