有向グラフの制約付き最大スパニングサブツリーの近似アルゴリズム

Question

有向グラフが与えられ、各ベクトルが負ではないコストを持ち、各頂点が非負の利益を持つ場合、どのようにスパニングサブツリーを見つけるか最大の利益を持つグラフ？私は、予算が所与の予算に比べて小さいことを拘束したい。私は、多項式時間の複雑さと理論的近似係数で問題の近似アルゴリズムを探しています。

Answer 1

スパニングツリーサブ

私はあなたがarborescenceを意味していることを前提とするつもりです。ルートuを修正する（または| V |の余分な要素についてはすべての頂点を試してみる）。すべての円弧についての場合、x を樹木のメンバーシップのための0-1インジケータ変数とする。すべての頂点についてvの場合は、y _vと同じにしてください。明らか整数プログラムは

∑ _V利益（V）Y _V
∑ コスト（）X を最大化です≤予算
＆forall; v ≠ u。 ＆すべてのために; S＆subseteq; V、U ∈ S、V ∉ S. Y _V ≤ ∑ _{∈ S ×（V＆setminus、S）}X
＆forall; a。 x_a ∈ {0,1}
; forall; v。 Y _V ∈ {0、1}

残念ながら、完全性ギャップが無限大です。他のいくつかの公式で同じ問題を抱えた後、近似率が“の近似率の近似アルゴリズムがないことをかなり強く疑うようになり始めています。この問題は、バイ・アット・バルク・メカニックと予算上の最大カバレッジ問題を組み合わせることで、追加カバレッジの限界費用を極度に安くすることが可能になります。近似を排除するような種類のスレッシュホールド動作につながるはずです。1つの方法は、bicriteria近似を解決することである（すなわち、近似アルゴリズムにより大きな予算を与える）。