On the Maximum Weighted Independent Set Problem with applications in wireless sensor networks

The Maximum Weighted Independent Set (MWIS) Problem considers a graph with weights assigned to the nodes and seeks to discover the "heaviest" independent set, that is, a set of nodes with maximal total weight so that no two nodes in the set are connected by an edge. The MWIS problem arises in many application domains including maximum a posteriori estimation, error-correcting coding, spatial statistics, and communication networks. It has been shown to be combinatorially hard (NP-complete ) and there has been extensive work in the literature proposing a variety of heuristics. In this dissertation, we propose a novel, low-complexity and distributed algorithm that yields high-quality feasible solutions to this problem.;Our proposed algorithm consists of two phases, each of which requires only local information and is based on message-passing between neighboring nodes. The first phase solves Linear Programming (LP) relaxations of the MWIS problem. We consider two LP relaxations: one involving simple edge constraints and another which is tighter and accounts for all cliques of the graph. The second phase of our algorithm uses the solution of the relaxation and constructs a feasible solution to the MWIS problem. We establish that we always obtain a feasible solution to MWIS and that for special cases of graphs the solution is optimal. More specifically, with the clique-based relaxation we can guarantee an optimal solution for the large class of so called perfect graphs. When using the edge-based relaxation, our algorithm guarantees optimality for bipartite graphs and obtains with high probability near-optimal solutions for general graphs with large weights. We also establish that our algorithms can run in an asynchronous fashion and provide the same optimality guarantees as the synchronous version.;We apply our algorithms to two different applications in wireless sensor networks. The first application concerns the problem of efficiently "emptying" a wireless sensor network that has accumulated a large amount of data at its nodes and seeks to relay them to designated gateways so as to maximize a concave function of achievable transmission rates. The other application is the problem of scheduling wireless networks with stochastic packet arrivals on the links and constant transmission rates. In both cases we show that our algorithms lead to significant performance gains over the current state-of-the art.