セミナー1日目終了。 今日の後半はあまりわからなかった。 修行不足を実感。

明後日からセミナーです。 いっぱい勉強するぞ！！

〇〇が「形容詞」という定義を導入したとき(導入したものは形容詞部分)、 「non-形容詞」は導入なしに使ってよいものだろうか。 読む側からすれば、定義していなくても意味を取ることはできるだろうが、 論文などではちゃんとしたほうがいいのかな？

Amortized Analysisをわかっている気でいいたけど、 必要になって初めてちゃんとした理解が得られたような気がする

凸集合Sの点の凸結合は,Sに含まれるということ

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

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

引き続き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-近似アルゴリズムになる。 近似アルゴリズムの知識は余り無いので、これを機に勉強する。 今日は２章まで読んで寝よう。

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