HLPP2010

平和に終了．

maximum matching の Karp-Sipser アルゴリズムをBSPモデルで並列化したという話があったのだけど…　結局のところ厳密ではない greedy アルゴリズムなので大外れの際にどれくらい最適解から外れるのかが気になった．元の Karp-Sipser アルゴリズムの時点での近似率も分からないのだけど，並列化によって明らかに近似率が悪くなる方向になっているのでどうなんだろうかと．まあ，実験を見る限りにおいてはリーズナブルに問題ないようだったけど…

閑話休題．

invited speak で tree 上の maximum independent set 問題が少しだけ話に上がった．この問題が木のサイズに関してリニアの仕事量で解ける（しかも O(n/p + log n) の並列時間できれいに並列計算できる）のは知っていたので，一般のグラフの上ではどうなるんだろうと疑問に思った．で，ちょっと考えてみたら，minimum vertex cover 補集合が maximum independent set になるということに気が付いて思考終了．つまらないなぁ…