II-nd stone: 屈辱の二撃

--What happened today--
今日は３連休に続いて４日目のオフ。気持ちよく休日を過ごしているところへ、友人からのメール「本日履修登録締切日」と。
すっかり頭からぬけきっていたため、慌てて学校へいって登録。登録も終了してほっとしているところへ今日の屈辱の２撃が。

第１撃
今日、後輩I君からminimum vertex coverの近似アルゴリズムの質問を受ける。
これと等価なmaximum independent setを研究していた身で質問に答えられなくて、結構屈辱的。一から勉強しなおしだ。
頂点の次数の高い順にとっていくという単純なものだが、このアルゴリズムの近似率がTheta(lg n)になるというのが理解できず（涙
ひとつlg n 倍になるインスタンスを見つければ下界だけでもいえるのだが。その後、自分で作ることができたわけではないが、googleで発見。
lg n　の近似率のところは\sum 1/k =O(lg n)を利用。

bipartite(L,R) graph を作る。Lは最適解,Rはgreedy solution.
|L|=m, |R|=(m+m/2+...+m/m)edgeの張り方は、以下のとおり
・それぞれのm/i 個のR内の頂点からはLのi個の頂点へ重なることなくedgeをはるすなわち、m/i 個のうちひとつの頂点からはi本のedgeをLのi個の頂点へ張る。そしてm/i個のうちのどの２つも共通のLの頂点へ辺は引かないようにする。

こうすることで、greedy ではRを、最適解はL であるので
|R|/|L|=lg n となり、めでたしめでたし。
あとは上界の証明がのこる。木曜のゼミを待とう。

第２撃
自分の居室とは別の部屋で後輩I君とmin vertex coverについて話していると、別の後輩のH君が登場。挨拶をしてみたが、鼻であしらわれる。かなり挑戦的な態度だった。

ぜんぜん関係ないが、ヤフオクでLoveStories I,II,IIIがセットで現在5250円だった。どうしようかな。迷うなぁ。