Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems
Point-to-Multipoint systems are a 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 o...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_02545330_v150_n1_p159_Marenco |
| Aporte de: |
| id |
todo:paper_02545330_v150_n1_p159_Marenco |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_02545330_v150_n1_p159_Marenco2023-10-03T15:11:33Z Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems Marenco, J.L. Wagler, A.K. Bandwidth allocation Polyhedral combinatorics Point-to-Multipoint systems are a 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 a combinatorial optimization problem, the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard and it is known that, for these problems, there exist no polynomial time algorithms with a fixed approximation ratio. Algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems. 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. © Springer Science+Business Media, LLC 2007. Fil:Marenco, J.L. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_02545330_v150_n1_p159_Marenco |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Bandwidth allocation Polyhedral combinatorics |
| spellingShingle |
Bandwidth allocation Polyhedral combinatorics Marenco, J.L. Wagler, A.K. Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems |
| topic_facet |
Bandwidth allocation Polyhedral combinatorics |
| description |
Point-to-Multipoint systems are a 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 a combinatorial optimization problem, the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard and it is known that, for these problems, there exist no polynomial time algorithms with a fixed approximation ratio. Algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems. 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. © Springer Science+Business Media, LLC 2007. |
| format |
JOUR |
| author |
Marenco, J.L. Wagler, A.K. |
| author_facet |
Marenco, J.L. Wagler, A.K. |
| author_sort |
Marenco, J.L. |
| title |
Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems |
| title_short |
Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems |
| title_full |
Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems |
| title_fullStr |
Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems |
| title_full_unstemmed |
Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems |
| title_sort |
chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems |
| url |
http://hdl.handle.net/20.500.12110/paper_02545330_v150_n1_p159_Marenco |
| work_keys_str_mv |
AT marencojl chromaticschedulingpolytopescomingfromthebandwidthallocationprobleminpointtomultipointradioaccesssystems AT waglerak chromaticschedulingpolytopescomingfromthebandwidthallocationprobleminpointtomultipointradioaccesssystems |
| _version_ |
1782028476058959872 |