Artículo
Abstract:
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.
Registro:
| Documento: | Artículo |
| Título: | Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems |
| Autor: | Marenco, J.L.; Wagler, A.K. |
| Filiación: | Departamento de Computación, FCEN, Ciudad Universitaria, (1428) Buenos Aires, Argentina Otto-von-Guericke-University of Magdeburg, Faculty of Mathematics/IMO, Universitätsplatz 2, 39106 Magdeburg, Germany |
| Palabras clave: | Bandwidth allocation; Polyhedral combinatorics |
| Año: | 2007 |
| Volumen: | 150 |
| Número: | 1 |
| Página de inicio: | 159 |
| Página de fin: | 175 |
| DOI: | http://dx.doi.org/10.1007/s10479-006-0156-y |
| Título revista: | Annals of Operations Research |
| Título revista abreviado: | Ann. Oper. Res. |
| ISSN: | 02545330 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v150_n1_p159_Marenco |
Referencias:
- Bley, A., Eisenblätter, A., Grötschel, M., Wagler, A., Wessäly, R., (1999) Frequenzplanung für Punkt- zu Mehrpunkt-Funksysteme, , Abschlußbericht eines Projekts der BOSCH Telecom GmbH und des Konrad-Zuse-Zentrums für Informationstechnik Berlin
- Brucker, P., (1998) Scheduling Algorithms, , Springer-Verlag
- Bixby, R.E., M. Ienelon, A. Gu, E. Rothberg, and R. Wunderling. (2004). Mixed-Integer Programming: A Progress Report. In M. Grötschel (Ed.), The Sharpest Cut: The Impact of Manfred Padberg and His Work. Philadelphia: SIAM/MPS Series on Optimization 4; de Werra, D., Gay, Y., Chromatic Scheduling nd Frequency Assignment (1994) Discrete Appl, Math, 49, pp. 165-174
- de Werra, D., Hertz, A., Consecutive Colorings of Graphs (1988) ZOR, 32, pp. 1-8
- Garey, M., Johnson, D., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , W.H. Freeman and Company
- Gerhardt, A., (1999) Polyedrische Untersuchungen von Zwei-Maschinen-Scheduling-Problemen mit Antipar-allelitätsbedingungen, , Master thesis, Technische Universität Berlin
- Golumbic, M.C., (1980) Algorithmic Graph Theory and Perfect Graphs, , Academic Press
- Kubale, M., Interval Vertex-Coloring of a Graph With Forbidden Colors (1989) Discrete Math, 74, pp. 125-136
- Marenco, J., (2005) Chromatic Scheduling Polytopes Coming from the. Bandwidth Allocation Problem in Point-to-Multipoint Radio Access Systems, , Ph.D thesis, Universidad de Buenos Aires
- Nemhauser, G., Wolsey, L., (1988) Integer Programming and Combinatorial Optimization, , John Wiley & Sons
- Wolsey, L., (1998) Integer Programming, , John Wiley & Sons
Citas:
---------- APA ----------
Marenco, J.L. & Wagler, A.K. (2007) . Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems. Annals of Operations Research, 150(1), 159-175.http://dx.doi.org/10.1007/s10479-006-0156-y
---------- CHICAGO ----------
Marenco, J.L., Wagler, A.K. "Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems" . Annals of Operations Research 150, no. 1 (2007) : 159-175.http://dx.doi.org/10.1007/s10479-006-0156-y
---------- MLA ----------
Marenco, J.L., Wagler, A.K. "Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems" . Annals of Operations Research, vol. 150, no. 1, 2007, pp. 159-175.http://dx.doi.org/10.1007/s10479-006-0156-y
---------- VANCOUVER ----------
Marenco, J.L., Wagler, A.K. Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems. Ann. Oper. Res. 2007;150(1):159-175.http://dx.doi.org/10.1007/s10479-006-0156-y
