کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652737 | 1632595 | 2010 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Cross line and column generation for the cut covering problem in wireless networks
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 36, 1 August 2010, Pages 255-262
Journal: Electronic Notes in Discrete Mathematics - Volume 36, 1 August 2010, Pages 255-262