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

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

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

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