Probability and Computing

Probability and Computing: Randomized Algorithms and Probabilistic Analysis
最近研究室で購入したものを読み始めている．
Randomized Algorithmsに関する本．いろいろとApplicationが載っていてなかなか面白い．1章の最後にでてきたRandomized min-cut algorithmというのが結構強くて，与えられたグラフに対して枝をRandomに選択して縮約すると1/n^2でmin-cutが出力されるというもの，証明はmin-cutの大きさをkとしたときに全ての頂点の次数はk以上だということを使う．
前原さんに聞いたところ，もうちょっと賢い枝の選び方をする方法が知られていて，Karger's algorithmとかいうらしい．
参考：
A New Approach to the Minimum Cut Problem