貪婪集覆蓋算法建*由*刪除*集

Question

我試圖用貪婪算法實現設置覆蓋問題的解決方案。

它經典的貪心近似算法是

input: collection C of sets over universe U , costs: C→R ≥0  
output: set cover S 
1. Let S←∅. 
2. Repeat until S covers all elements: 
3. Add a set s to S, where s∈C maximizes the number of elements in s not yet covered by set s in S, divided by the cost c(s). 
4. Return S. 

我有兩個部分問題：

一個。反向算法是否是有效算法，即

input: collection C of sets over universe U , costs: C→R ≥0  
output: set cover S 
1. Let S←C . 
2. Repeat until there are no s∈S such that S-s=S (i.e. all elements in s are redundant): 
3. Remove a set s from S, where s∈S minimises the number of elements in s, divided by the cost c(s). 
4. Return S. 

b。問題的本質是容易得到C，並且會有一個有限數量的冗餘集合 - 在這種情況下，這個算法的性能會更好嗎？

Answer 1

該算法肯定會返回一個有效的集合封面，因爲它在每一步檢查是否所有s元素都是多餘的。 直覺上我覺得b部分是真實的，儘管我無法寫出正式的證明。請閱讀Vijay Vazirani的第2章，因爲它可能有助於分析部分。