- 2007-09-05 (Wed) 05:38
- アカデミック？
Tree Partitioning の話が出る：「木のノードに非負の重みがつけられている．木から k-1 本の片を取り除いて k 個の木に分割する．分割された木の重さを，それに含まれるノードの重みの和とする．このとき，分割された木の重さの最大を最小にする分割を求めよ．」
最後の部分は最小を最大にするとか，最小ないし最大を制限するとかの派生がある．んで，この問題自体は多項式ないし線形オーダーのアルゴリズムがあるらしい．多項式のやつに関してはセパレータを適当にシフトしてくだけでよいらしい．max-min は簡単なシフトのみ， min-max は二種類のシフトを使うとのこと．証明追ってるけどシフトのみでいけるってのは面白いなぁ．
- Newer: ことはじめ