algorithm - 頂点の重みが負になる可能性がある場合の最大重み独立集合の近似アルゴリズム

Question

最大重み独立集合には多くの近似アルゴリズムがあります。しかし、それらのほとんどは、非負の重みを想定しています。可能な負の重みに対して機能するアルゴリズムはありますか?

Answer 1

重みが負の頂点を無視します。負の重みの頂点を含む独立集合を考えてみましょう。その頂点を削除すると、結果のセットは独立したセットのままですが、合計の重みが増加します。