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:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2007
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 05344caa a22005297a 4500 | ||
|---|---|---|---|
| 001 | PAPER-6692 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203624.0 | ||
| 008 | 190411s2007 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-33846872385 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Marenco, J.L. | |
| 245 | 1 | 0 | |a Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems |
| 260 | |c 2007 | ||
| 270 | 1 | 0 | |m Marenco, J.L.; Departamento de Computación, FCEN, Ciudad Universitaria, (1428) Buenos Aires, Argentina; email: jmarenco@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a 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 | ||
| 504 | |a Brucker, P., (1998) Scheduling Algorithms, , Springer-Verlag | ||
| 504 | |a 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 | ||
| 504 | |a de Werra, D., Hertz, A., Consecutive Colorings of Graphs (1988) ZOR, 32, pp. 1-8 | ||
| 504 | |a Garey, M., Johnson, D., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , W.H. Freeman and Company | ||
| 504 | |a Gerhardt, A., (1999) Polyedrische Untersuchungen von Zwei-Maschinen-Scheduling-Problemen mit Antipar-allelitätsbedingungen, , Master thesis, Technische Universität Berlin | ||
| 504 | |a Golumbic, M.C., (1980) Algorithmic Graph Theory and Perfect Graphs, , Academic Press | ||
| 504 | |a Kubale, M., Interval Vertex-Coloring of a Graph With Forbidden Colors (1989) Discrete Math, 74, pp. 125-136 | ||
| 504 | |a 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 | ||
| 504 | |a Nemhauser, G., Wolsey, L., (1988) Integer Programming and Combinatorial Optimization, , John Wiley & Sons | ||
| 504 | |a Wolsey, L., (1998) Integer Programming, , John Wiley & Sons | ||
| 520 | 3 | |a 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. |l eng | |
| 536 | |a Detalles de la financiación: Secretaría de Ciencia y Técnica, Universidad de Buenos Aires, X036 | ||
| 536 | |a Detalles de la financiación: Agencia Nacional de Promoción Científica y Tecnológica, 11-09112 | ||
| 536 | |a Detalles de la financiación: Consejo Nacional de Investigaciones Científicas y Técnicas, 644/98 | ||
| 536 | |a Detalles de la financiación: Deutsche Forschungsgemeinschaft, Gr 883/9–1 | ||
| 536 | |a Detalles de la financiación: J. L. Marenco: This work supported by UBACYT Grant X036, CONICET Grant 644/98 and ANPCYT Grant 11-09112. | ||
| 536 | |a Detalles de la financiación: A. K. Wagler: This work supported by the Deutsche Forschungsgemeinschaft (Gr 883/9–1). | ||
| 593 | |a Departamento de Computación, FCEN, Ciudad Universitaria, (1428) Buenos Aires, Argentina | ||
| 593 | |a Otto-von-Guericke-University of Magdeburg, Faculty of Mathematics/IMO, Universitätsplatz 2, 39106 Magdeburg, Germany | ||
| 690 | 1 | 0 | |a BANDWIDTH ALLOCATION |
| 690 | 1 | 0 | |a POLYHEDRAL COMBINATORICS |
| 700 | 1 | |a Wagler, A.K. | |
| 773 | 0 | |d 2007 |g v. 150 |h pp. 159-175 |k n. 1 |p Ann. Oper. Res. |x 02545330 |t Annals of Operations Research | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-33846872385&doi=10.1007%2fs10479-006-0156-y&partnerID=40&md5=99be789ed9c6486ff203a3e09490b731 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s10479-006-0156-y |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_02545330_v150_n1_p159_Marenco |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v150_n1_p159_Marenco |y Registro en la Biblioteca Digital |
| 961 | |a paper_02545330_v150_n1_p159_Marenco |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 67645 | ||