Cross Line and Column Generation for the Cut Covering Problem in Wireless Networks - Archive ouverte HAL Access content directly
Conference Papers Year : 2010

Cross Line and Column Generation for the Cut Covering Problem in Wireless Networks

(1) , (2) , (3)
1
2
3
Christelle Caillouet
Hervé Rivano

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.
Not file

Dates and versions

inria-00466485 , version 1 (24-03-2010)

Identifiers

Cite

Christelle Caillouet, Stéphane Pérennes, Hervé Rivano. Cross Line and Column Generation for the Cut Covering Problem in Wireless Networks. International Symposium on Combinatorial Optimization (ISCO 2010), 2010, Hammamet, Tunisia. pp.255-262, ⟨10.1016/j.endm.2010.05.033⟩. ⟨inria-00466485⟩
184 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More