Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks supplying wireless access to voice/data communication networks to customers with individual communication demands. This bandwidth allocation problem is a special chromatic scheduling problem; both problems are N P-complete and, furthermore, there exist no polynomial-time algorithms with a fixed quality guarantee for them. As algorithms based on cutting planes are shown to be successful for many other combinatorial optimization problems, the goal is to apply such methods to the bandwidth allocation problem. For that, knowledge on the associated polytopes is required. The present paper contributes to this issue, introducing new classes of valid inequalities based on variations and extensions of the covering-clique inequalities presented in [J. Marenco, Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems, Ph.D. Thesis, Universidad de Buenos Aires, Argentina, 2005; J. Marenco, A. Wagler, Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems, Annals of Operations Research 150-1 (2007) 159-175]. We discuss conditions ensuring that these inequalities define facets of chromatic scheduling polytopes, and we show that the associated separation problems are N P-complete. © 2008 Elsevier B.V. All rights reserved.
Documento: | Artículo |
Título: | Facet-inducing inequalities for chromatic scheduling polytopes based on covering cliques |
Autor: | Marenco, J.; Wagler, A. |
Filiación: | Computer Science Dept., FCEN, University of Buenos Aires Pabellón I, Ciudad Universitaria, 1428 Buenos Aires, Argentina Sciences Institute, National University of General Sarmiento, J. M. Gutierrez J. Verdi, Malvinas Argentinas, 1613 Buenos Aires, Argentina Institute for Mathematical Optimization, Faculty for Mathematics, Otto-von-Guericke University of Magdeburg, Universitätsplatz 2, 39106 Magdeburg, Germany |
Palabras clave: | Bandwidth allocation; Facets; Polyhedral combinatorics; Separation; Bandwidth; Combinatorial mathematics; Combinatorial optimization; Isomers; Radio; Scheduling; Telecommunication systems; Wireless networks; Bandwidth allocation; Bandwidth allocation problems; Buenos aires , argentina; Chromatic scheduling; Combinatorial optimization problems; Communication networks; Cutting planes; Facets; New classes; Polyhedral combinatorics; Polytopes; Quality guarantees; Radio access networks; Radio accesses; Separation problems; Solution sets; Time algorithms; Valid inequalities; Wireless accesses; Topology |
Año: | 2009 |
Volumen: | 6 |
Número: | 1 |
Página de inicio: | 64 |
Página de fin: | 78 |
DOI: | http://dx.doi.org/10.1016/j.disopt.2008.09.002 |
Título revista: | Discrete Optimization |
Título revista abreviado: | Discrete Optim. |
ISSN: | 15725286 |
PDF: | https://bibliotecadigital.exactas.uba.ar/download/paper/paper_15725286_v6_n1_p64_Marenco.pdf |
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v6_n1_p64_Marenco |