WATAPEDIA
--
数学
-- 最適化問題
Last updated Dec. 10, 2015
Home
Return
PDFを表示
記事が表示されない場合は，ブラウザが非対応です．<br>上のPDFを表示をクリックしてください．<br><br><br><br><br><br><br>comp -MYPEDIA Math- 最適化問題 Optimization problem 1 概要 ここでは，種々の最適化問題をまとめる． 2 Min Sum Set Cover Problem 問題 hypergraph H(V, E) に対して，ノード V から {1, . . . , |V |} への写像を f とする．また，写像 f に対して，f(e) を minv∈e f(v) と定義する．こ のとき， ∑ e f(e) を最小化する f を見つける問題を Min sum set cover problem と呼ぶ． hypergraph はグラフを一般化したもので，通常のグラフのエッジが 2 つのノード をつなぐのに対して，hypergraph におけるエッジは任意個数のノードをつなぐ． 例えば，f によりノードを調べる順番だと捉え，エッジに所属するノードのうち 少なくとも一つのノードを調べればそのエッジを調べられるとしたときに，すべて のエッジを調べるのに要する時間を最小化するような問題に相当する．hypergraph をグラフに限定する場合，Min sum vertex cover problem と呼ぶ． 当然 NP-hard なので，greedy algorithm が Uriel Feige らによって提案されている [1]． 参考文献 : [1] U. Feige, L. Lov´ asx, and P. Tetali, “Approximating Min-sum Set Cover,” Algo- rithmica, vol. 40, no. 4, pp. 219–234, dec 2004. 1 Math 一覧へ . ↰.