On The Algorithms For Two Variants Of Set Cover Problem

In this thesis, we study two variants of set cover problem.The first variant of set cover problem:in wireless networks, each node needs to select one channel from its available channels as the control channel to transmit protocol or signal information with its neighbor nodes. To transmit protocol or signal information, each control channel needs to occupy spectrum bandwidth.In order to optimize the usage of the limited spectrum resources, this thesis focuses on the issue of control channel selection. The problem is how to select the set of control channels for the whole wireless network which minimizes the total spectrum bandwidth of the control channels. We propose a greedy algorithm which minimizes the total spectrum bandwidth of the set of control channels. Theoretical analysis proves that the proposed algorithm can achieve the optimal set of control channels whose sum of the spectrum band-width is the minimum. Simulation results also show that the proposed algorith-m consumes less spectrum resource than other algorithms in the same wireless network environment.The other variant is relevant to set cover game, named cover-sets games. Different from the traditional set cover game, where the elements are service receivers and the subsets are service providers, each player i is a service receiver and may also be chosen as a service provider in cover-sets games, where 1< i?m. Each player i as a service receiver hopes to receive the set of service si and also can provide the set of services si' if it is chosen as a service provider. Let S={s1,s2, …,sm} and S={s1',s2',…,sm'} be a collection of subsets of a universal set U={e1, e2,…,en}. We develop for cover-sets games a general cost allocation methods that is approximately budget-balanced and in the core. The cost allocation method always recovers 1/H(K) fraction of the optimal total cost, where K= maxsj'?S'?si?S|sj'?si| and H(K) is the harmonic function. When the player to be served are selfish receivers with private valuations, we present a strategyproof charging mechanism, and the total cost of the output is not more than H(K) times of the optimal solution. When the elements are selfish providers with private costs, we also present a strategyproof payment mechanism to them.