Facet-inducing inequalities for chromatic scheduling polytopes based on covering cliques
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 sched...
| Autores principales: | , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_15725286_v6_n1_p64_Marenco |
| Aporte de: |
| id |
todo:paper_15725286_v6_n1_p64_Marenco |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_15725286_v6_n1_p64_Marenco2023-10-03T16:27:21Z Facet-inducing inequalities for chromatic scheduling polytopes based on covering cliques Marenco, J. Wagler, A. 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 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. 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_p64_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 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 |
| spellingShingle |
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 Marenco, J. Wagler, A. Facet-inducing inequalities for chromatic scheduling polytopes based on covering cliques |
| topic_facet |
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 |
| description |
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. |
| format |
JOUR |
| author |
Marenco, J. Wagler, A. |
| author_facet |
Marenco, J. Wagler, A. |
| author_sort |
Marenco, J. |
| title |
Facet-inducing inequalities for chromatic scheduling polytopes based on covering cliques |
| title_short |
Facet-inducing inequalities for chromatic scheduling polytopes based on covering cliques |
| title_full |
Facet-inducing inequalities for chromatic scheduling polytopes based on covering cliques |
| title_fullStr |
Facet-inducing inequalities for chromatic scheduling polytopes based on covering cliques |
| title_full_unstemmed |
Facet-inducing inequalities for chromatic scheduling polytopes based on covering cliques |
| title_sort |
facet-inducing inequalities for chromatic scheduling polytopes based on covering cliques |
| url |
http://hdl.handle.net/20.500.12110/paper_15725286_v6_n1_p64_Marenco |
| work_keys_str_mv |
AT marencoj facetinducinginequalitiesforchromaticschedulingpolytopesbasedoncoveringcliques AT waglera facetinducinginequalitiesforchromaticschedulingpolytopesbasedoncoveringcliques |
| _version_ |
1807323903681363968 |