各ベクトルに負でないコストがあり、各頂点に負でない利益がある有向グラフが与えられた場合、利益が最大になるグラフのスパニング サブツリーをどのように見つけますか? コストを特定の予算に抑える必要があります。多項式時間の複雑さと理論上の近似係数の問題の近似アルゴリズムを探しています。
1 に答える
1
スパニングサブツリー
私はあなたがarborescenceを意味したと仮定します。ルート u を修正します (または、余分な係数 |V| についてすべての頂点を試します)。すべての弧aについて、x aを樹木のメンバーシップの 0-1 指示変数とします。すべての頂点vについて、y vを同じにします。明らかな整数プログラムは
∑ v利益 ( v ) y v
∑ aコスト ( a ) x a ≤ 予算
∀ v ≠ uを最大化します。∀ S ⊆V, u∈ S , v ∉S. y v ≤ ∑ a ∈ S ×(V∖ S ) x a
∀ a . x a ∈ {0, 1}
∀ v . y v ∈ {0, 1}
残念ながら、完全性のギャップは無限大です。他のいくつかの定式化で同じ問題を抱えた後、「合理的な」近似比を持つ近似アルゴリズムが存在しないことをかなり強く疑うようになりました. この問題は、一括購入メカニズムと予算による最大補償範囲の問題を組み合わせたものであり、追加補償の限界費用が非常に安くなる可能性があります。 . 解決策の 1 つは、二基準近似で解決することです (つまり、近似アルゴリズムにより大きなバジェットを与えます)。
于 2012-03-29T17:16:43.910 に答える