針對有向圖的約束最大生成子樹的逼近算法

Question

給定一個有向圖，其中每個向量具有非負成本並且每個頂點具有非負利潤，那麼如何找到生成子樹的生成子樹最大利潤的圖表？我想限制成本更小到給定的預算。我正在尋找多項式時間複雜度問題的近似算法和理論近似因子。

Answer 1

生成樹子樹

我會假設你的意思是一個arborescence。修復一個root u（或者只是嘗試所有頂點的額外因子| V |）。對於每個圓弧a，讓x _a是樹狀成員資格的0-1指示變量。對於每個頂點v，讓y _v是相同的。明顯的整數程序是

最大化∑ _v利潤（v）ý _v
∑ _一個成本（一個）X _一個 ≤預算
＆forall; v ≠ u。 ＆對全部; 小號＆subseteq; V，U ∈ 小號，v ∉ S. ý _v ≤ ∑ _{一個 ∈ 小號 ×（V＆setminus; 小號）}X _一個
＆forall; a。 x _a ∈ {0，1}
＆forall; v。 ÿ _v ∈ {0，1}

不幸的是，完整性間隙是無限的。在與其他幾個公式遇到同樣的問題後，我開始相當強烈地懷疑，沒有近似算法與近似比例的合理的。這種問題將大批量購買機制與預算最大覆蓋問題結合起來，使附加覆蓋的邊際成本變得非常便宜，這看起來好像應該導致排除近似值的閾值行爲。一種解決辦法可能是解決雙標準近似（即給出近似算法更大的預算）。