Cycle-based facets of chromatic scheduling polytopes
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 po...
| Autor principal: | |
|---|---|
| Publicado: |
2009
|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v6_n1_p51_Marenco http://hdl.handle.net/20.500.12110/paper_15725286_v6_n1_p51_Marenco |
| Aporte de: |
| id |
paper:paper_15725286_v6_n1_p51_Marenco |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_15725286_v6_n1_p51_Marenco2023-06-08T16:24:39Z Cycle-based facets of chromatic scheduling polytopes Marenco, Javier Leonardo 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 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. Fil:Marenco, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2009 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v6_n1_p51_Marenco http://hdl.handle.net/20.500.12110/paper_15725286_v6_n1_p51_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 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 |
| spellingShingle |
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 Marenco, Javier Leonardo Cycle-based facets of chromatic scheduling polytopes |
| topic_facet |
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 |
| description |
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. |
| author |
Marenco, Javier Leonardo |
| author_facet |
Marenco, Javier Leonardo |
| author_sort |
Marenco, Javier Leonardo |
| title |
Cycle-based facets of chromatic scheduling polytopes |
| title_short |
Cycle-based facets of chromatic scheduling polytopes |
| title_full |
Cycle-based facets of chromatic scheduling polytopes |
| title_fullStr |
Cycle-based facets of chromatic scheduling polytopes |
| title_full_unstemmed |
Cycle-based facets of chromatic scheduling polytopes |
| title_sort |
cycle-based facets of chromatic scheduling polytopes |
| publishDate |
2009 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v6_n1_p51_Marenco http://hdl.handle.net/20.500.12110/paper_15725286_v6_n1_p51_Marenco |
| work_keys_str_mv |
AT marencojavierleonardo cyclebasedfacetsofchromaticschedulingpolytopes |
| _version_ |
1768542430040162304 |