Skip to Main content Skip to Navigation
Conference papers

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

Christelle Caillouet 1 Stéphane Pérennes 2 Hervé Rivano 3
1 Drakkar
LIG - Laboratoire d'Informatique de Grenoble
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
3 SWING - Smart Wireless Networking
Inria Grenoble - Rhône-Alpes, CITI - CITI Centre of Innovation in Telecommunications and Integration of services
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.
Document type :
Conference papers
Complete list of metadatas
Contributor : Hervé Rivano <>
Submitted on : Wednesday, March 24, 2010 - 12:31:57 AM
Last modification on : Tuesday, December 8, 2020 - 10:41:01 AM



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⟩



Record views