On the Algorithms for Two Variants of Set Cover Problem.pdf

1、本文研究了兩類集合覆蓋的變形問題。
　　第一類集合覆蓋的變形問題:無線網絡中，每個節(jié)點需要從可用信道中選擇一個信道作為控制信道，用于傳輸協議和信令信息。在傳輸信息的過程中，每個信道都會占用一定量的頻譜帶寬。為了最少的占用有限的頻譜資源，本文中主要研究控制信道的選擇問題。一個自然的問題是，如何選擇控制信道使得整個網絡中控制信道所占的總的頻譜帶寬最小。我們設計了貪婪算法使得控制頻道集合的全部頻譜帶寬的和最小。定理分析證明了設計的算法可

2、以達到最優(yōu)的控制頻道集合且其頻譜帶寬的總和最小。同時，模擬結果證明了在同樣的無線網絡環(huán)境中設計的算法比其它算法消耗的頻譜資源少。
　　第二類變形問題與集合覆蓋博弈相關，即覆蓋集合博弈。覆蓋集合博弈不同于傳統的集合覆蓋博弈，在集合覆蓋博弈中元素作為服務的接受者，且子集作為服務的提供者，而在覆蓋集合博弈中每一個參與者i，1≤i≤m，既是服務接受者而且可能被選取為服務的提供者。參與者i作為服務接受者希望得到的服務集合為si而被選取為服務

3、提供者可提供的服務集合為s'i。令S={s1，s2，…，sm}且S'={s'1，s'2，…，s'm}是有限集合U={e1，e2，…，en}的子集組成的集合。對于覆蓋集合博弈，我們設計的費用分配方案滿足1/H(K)-近似預算平衡且在核中，其中K=maxs'j∈S'∑si∈S|s'j∩ si|且H(K)是調和級數。當參與者作為自私的服務接受者且擁有個人的私有費用信息時，我們設計了索價占優(yōu)策略機制，進一步得到該機制中分攤費用的總和不大于最優(yōu)解