ランダマイズドな近似アルゴリズムに関する論文は読みにくい

ランダマイズドアルゴリズムや近似アルゴリズムには，平均の計算量とか近似比とかをコントロールする為のパラメータが含まれる．そして，多くの場合，ランダム選択のための確率や条件分岐の条件には，そのパラメータの一見して意味不明な多項式とかが大量に出てくる．基本的にこれらの式の形の複雑さは，計算量とかの保証のために証明上都合の良いしきい値を取っていることに起因する．そのため，アルゴリズム中のパラメータによる判定式が何の目的でその形をしているのかは証明を詳しく追わないと理解出来ない．とどのつまり，直感が働かないのでアルゴリズムの本質がなんなのか一見しただけではわからない（論文の本文中に説明があれば別なのだけど，紙面の都合上，そこまで親切にするのは難しいのでしょう）．

ということで，Max-cover を解くためのランダマイズド近似並列アルゴリズムの論文読むのに二日かかった．MapReduce使えるとか言っているのを確かめたかっただけなので，そこまで細かく読む必要はなかったかもしれない．

そしてこいつは GroupByKey によって，「集合→含まれる要素達」という関係と「要素→それを含む集合達」という関係とをスイッチングするのがキモらしい．ということで，こういった視点の切り替えが必要な集合上のアルゴリズムならGBK演算が必要といえそう．他にっどんな問題があるのか良く解らんけど．

とりあえず Set-cover と Weighted Max-cover と BudgetありMax-cover も同じで動くでしょう．Set-cover はもっと単純かもしれんけど．