最も高密度のサブグラフを見つけるためのCharikarアルゴリズムが最適ではないのはなぜですか?

I read about the algorithm in Greedy Approximation Algorithms for Finding Dense
Components in a Graph
by Moses Charikar, and I tried to find an
instance/graph where the algorithm returns a different solution
from the optimal one but I didn’t succeed. Can anyone provide me an
example where the algorithm ‘fails’ and proves that the
approximation is no less than 2?

ベストアンサー

4つのノードに完全なグラフがあり、その次に4次のハブと4次の3つのサテライトを含む5つのノードを持つグラフがあるとします。欲張りアルゴリズムは、衛星の1つを取り除くことから始めることができ、したがって1.6
o ------- o o ------- o | /| | /| | X | | o | |/ | |/ | o
------- o o ------- o
完全性のために、グラフ$ G =(V、E)$が与えられれば、量$
{E}を最大化するサブセット$ S subseteq V $を見つけることが課題です。/| S | $ここで、$ E(S)
subseteq E $は、$ S
$で終点を持つ辺の集合です。欲張りアルゴリズムは、最小次数の頂点を連続的に除去し、続いて収縮する一連の残りの頂点の中から最適な$ S
$を探索することによって動作する。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です