On+the+Algorithms+for+Two+Variants+of+Set+Cover+Problem

《On+the+Algorithms+for+Two+Variants+of+Set+Cover+Problem》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据摘要本文研究了两类集合覆盖的变形问题。第一类集合覆盖的变形问题：无线网络中，每个节点需要从可用信道中选择一个信道作为控制信道，用于传输协议和信令信息。在传输信息的过程中，每个信道都会占用一定量的频谱带宽。为了最少的占用有限的频谱资源，本文中主要研究控制信道的选择问题。一个自然的问题是，如何选择控制信道使得整个网络中控制信道所占的总的频谱带宽最小。我们设计了贪婪算法使得控制频道集合的全部频谱带宽的和最小。定理分析证明了设计的算法可以达到最优的控制频道集合且其频谱带宽的总和最小。同时，模拟结果证明了在同样的无线网络环境中设计的算法比其它算法消耗的频谱资源少。

2、第二类变形问题与集合覆盖博弈相关，即覆盖集合博弈。覆盖集合博弈不同于传统的集合覆盖博弈，在集合覆盖博弈中元素作为服务的接受者，且子集作为服务的提供者，而在覆盖集合博弈中每～个参与者i，1≤i≤m，既是服务接受者而且可能被选取为服务的提供者。参与者i作为服务接受者希望得到的服务集合为si而被选取为服务提供者可提供的服务集合为s：。令S={81，82，⋯，sm)且∥=．[si，s：j，⋯，s二)是有限集合U={e1，e2，⋯，en，的子集组成的集合。对于覆盖集合博弈，我们设计的费用分配方案满足爿京．近似预算平衡且在核中，其中K=max。：∈s，∑。i∈s18；nSi

3、I且日(K)是调和级数。当参与者作为自私的服务接受者且拥有个人的私有费用信息时，我们设计了索价占优策略机制，进一步得到该机制中分摊费用的总和不大于最优解的日(K)倍。当参与者被选取为自私的服务提供者且拥有个人的私有成本信息时，我们设计了支付占优策略机制。关键词：控制信道；贪婪算法；集合覆盖；机制设计万方数据ContentsAbstract(inEnglish)．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．iAbstract(inChines‘0⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

4、⋯⋯⋯⋯．．iiiChapter1Introduction．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．11．1Thebackgroundofthecontrolchannelproblem．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．11．2RelatedworkandOUrresultsofthecontrolchannelproblem⋯⋯⋯⋯⋯．．11．3Mofivadonsandbackgroundofcover-setsgames．．．．．．．．．．．．．．．

5、．．．．．．．．．．．．．．31．4RelatedworkandOUrresultsofcover-setsgames．．．．．．．．．．．．．．．．．．．．．．．．．．．．．61．5Organizationofthesis．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．9Chapter2Theselectionofthecontrolchannels。．．．．．．．．．．．．．．．．．．。．．．．．．．。．．．．．．112．1AllocationAlgorithm．．．．．．．．．．．．．．

6、．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．112．2Evaluation．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．14Chapter3Costallocationandstrategyproofmechanismsforcover-setsgames⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．+⋯⋯⋯．173．1Costsharingamongunselfishplayers⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯173

7、．2Selfishplayersastheservicereceivers⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．223．3Selfishplayersastheserviceproviders⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．25Bibliography⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯29FinishedPapers⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯33Acknowledgements⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．34万方数据Chapter1Introduction1．1Thebackgroundofthecontrolch

8、annelproblem