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...
| Autores principales: | , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_15725286_v6_n1_p51_Marenco |
| Aporte de: |
| id |
todo:paper_15725286_v6_n1_p51_Marenco |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_15725286_v6_n1_p51_Marenco2023-10-03T16:27:20Z Cycle-based facets of chromatic scheduling polytopes Marenco, J. Wagler, A. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, J. Wagler, A. 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. |
| format |
JOUR |
| author |
Marenco, J. Wagler, A. |
| author_facet |
Marenco, J. Wagler, A. |
| author_sort |
Marenco, J. |
| 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 |
| url |
http://hdl.handle.net/20.500.12110/paper_15725286_v6_n1_p51_Marenco |
| work_keys_str_mv |
AT marencoj cyclebasedfacetsofchromaticschedulingpolytopes AT waglera cyclebasedfacetsofchromaticschedulingpolytopes |
| _version_ |
1807321561189842944 |