Publikationsdatum:
2020-08-05
Beschreibung:
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.
Schlagwort(e):
ddc:000
Sprache:
Englisch
Materialart:
reportzib
,
doc-type:preprint
Format:
application/postscript
Format:
application/pdf
Permalink
