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