Artículo
Marenco, J.; Wagler, A. "Cycle-based facets of chromatic scheduling polytopes" (2009) Discrete Optimization. 6(1):51-63
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks, which supply wireless access to voice/data communication for customers with fixed antennas and individual demands. This problem is N P-complete and, moreover, does not admit polynomial-time approximation algorithms with a fixed quality guarantee. As algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems, our goal is to apply such methods to the bandwidth allocation problem. To gain the required knowledge on the associated polytopes, the present paper contributes by considering three new classes of valid inequalities based on cycles in the interference graph. We discuss in which cases they define facets and explore the associated separation problems, showing that two of them are solvable in polynomial time. © 2008 Elsevier B.V. All rights reserved.
Registro:
| Documento: | Artículo |
| Título: | Cycle-based facets of chromatic scheduling polytopes |
| Autor: | Marenco, J.; Wagler, A. |
| Filiación: | Computer Science Department, 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; Competition; Isomers; Polynomial approximation; Scheduling; Telecommunication systems; Topology; Wireless networks; Bandwidth allocation; Bandwidth allocation problems; Chromatic scheduling; Combinatorial optimization problems; Cutting planes; Facets; Interference graphs; New classes; Polyhedral combinatorics; Polynomial times; Polytopes; Quality guarantees; Radio access networks; Separation problems; Solution sets; Valid inequalities; Wireless accesses; Approximation algorithms |
| Año: | 2009 |
| Volumen: | 6 |
| Número: | 1 |
| Página de inicio: | 51 |
| Página de fin: | 63 |
| DOI: | http://dx.doi.org/10.1016/j.disopt.2008.08.004 |
| Título revista: | Discrete Optimization |
| Título revista abreviado: | Discrete Optim. |
| ISSN: | 15725286 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v6_n1_p51_Marenco |
Referencias:
- Ahuja, R., Magnanti, T., Orlin, J., (1993) Network Flows: Theory, Algorithms and Applications, , Prentice Hall
- A. Bley, A. Eisenblätter, M. Grötschel, A. Wagler, R. Wessäly, Frequenzplanung für Punkt- zu Mehrpunkt-Funksysteme, Abschlußbericht eines Projekts der BOSCH Telecom GmbH und des Konrad-Zuse-Zentrums für Informationstechnik Berlin, 1999; Campêlo, M., Corrêa, R., Frota, Y., Cliques, holes and the vertex coloring polytope (2004) Information Processing Letters, 89, pp. 159-164
- de Werra, D., Gay, Y., Chromatic scheduling and frequency assignment (1994) Discrete Applied Mathematics, 49, pp. 165-174
- de Werra, D., Hertz, A., Consecutive colorings of graphs (1988) ZOR, 32, pp. 1-8
- Grötschel, M., Junger, M., Reinelt, G., Facets of the linear ordering polytope (1985) Mathematical Programming, 33, pp. 43-60
- Grötschel, M., Lovász, L., Schrijver, A., (1988) Geometric Algorithms and Combinatorial Optimization, , Springer Verlag
- Karp, R., A characterization of the minimum cycle mean in a digraph (1978) Discrete Mathematics, 23, pp. 309-311
- Karp, R., Orlin, J., Parametric shortest path algorithms with an application to cyclic staffing (1981) Discrete Applied Mathematics, 3, pp. 37-45
- Korte, B., Vygen, J., (2000) Combinatorial Optimization: Theory and Algorithms, , Springer Verlag
- 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. Available at: http://www.dc.uba.ar/inv/tesis/tesdoc/tesisMarenco.pdf; Marenco, J., Wagler, A., On the combinatorial structure of chromatic scheduling polytopes (2006) Discrete Applied Mathematics, 154-13, pp. 1865-1876
- Marenco, J., Wagler, A., Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems (2007) Annals of Operations Research, 150, pp. 159-175
- Marenco, J., Wagler, A., Facet-inducing inequalities for chromatic scheduling polytopes based on covering cliques (2008) Discrete Optimization, 6 (1), pp. 64-78
Citas:
---------- APA ----------
Marenco, J. & Wagler, A. (2009) . Cycle-based facets of chromatic scheduling polytopes. Discrete Optimization, 6(1), 51-63.http://dx.doi.org/10.1016/j.disopt.2008.08.004
---------- CHICAGO ----------
Marenco, J., Wagler, A. "Cycle-based facets of chromatic scheduling polytopes" . Discrete Optimization 6, no. 1 (2009) : 51-63.http://dx.doi.org/10.1016/j.disopt.2008.08.004
---------- MLA ----------
Marenco, J., Wagler, A. "Cycle-based facets of chromatic scheduling polytopes" . Discrete Optimization, vol. 6, no. 1, 2009, pp. 51-63.http://dx.doi.org/10.1016/j.disopt.2008.08.004
---------- VANCOUVER ----------
Marenco, J., Wagler, A. Cycle-based facets of chromatic scheduling polytopes. Discrete Optim. 2009;6(1):51-63.http://dx.doi.org/10.1016/j.disopt.2008.08.004
