Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652737 | Electronic Notes in Discrete Mathematics | 2010 | 8 Pages |
Abstract
In this paper, we address the problem of bandwidth allocation and routing in wireless networks. A first model of this problem is known as the Round Weighting Problem (RWP) in which a weight is assigned to the set of rounds, i.e. a set of pairwise non-interfering links. We present a new formulation that forgets about the routing and concentrate on the capacity available on the network cuts. We use the maximum flow/minimum cut theorem known in graph theory to develop the Cut Covering Problem (CCP) and prove that it computes equivalent optimal round weights than RWP. We develop a primal/dual algorithm combining line and column generation to deal with the exponential number of variables and constraints of CCP.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics