Chromatic Scheduling Polytopes coming from the Bandwidth Allocation Problem in Point-to-Multipoint Radio AccessSystems

Please always quote using this URN: urn:nbn:de:0297-zib-7614
  • Point-to-Multipoint systems are one kind of radio systems supplying wireless access to voice/data communication networks. Such systems have to be run using a certain frequency spectrum, which typically causes capacity problems. Hence it is, on the one hand, necessary to reuse frequencies but, on the other hand, no interference must be caused thereby. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there exist no polynomial time approximation algorithms with a guaranteed quality. One kind of algorithms which turned out to be successful for many other combinatorial optimization problems uses cutting plane methods. In order to apply such methods, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring basic properties of chromatic scheduling polytopes and several classes of facet-defining inequalities.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Javier Marenco, Annegret Wagler
Document Type:ZIB-Report
Tag:Bandwidth allocation; polyhedral combinatorics
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Date of first Publication:2003/11/26
Series (Serial Number):ZIB-Report (03-39)
Published in:Appeared in: Annals of Operations Research 150 (2007) 159-175