Combinatorial equivalence of Chromatic Scheduling Polytopes

Mostrar todas las versiones(2)

Point-to-Multipoint systems are one kind of radio systems supplying wireless access to voice/data communication networks. Capacity constraints typically force the reuse of frequencies but, on the other hand, no interference must be caused thereby. This leads to the bandwidth allocation problem, a sp...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Marenco, J., Wagler, A.
Formato: JOUR
Materias:
combinatorial equivalence
polyhedral combinatorics
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_15710653_v18_n_p177_Marenco
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_15710653_v18_n_p177_Marenco
record_format dspace
spelling todo:paper_15710653_v18_n_p177_Marenco2023-10-03T16:26:59Z Combinatorial equivalence of Chromatic Scheduling Polytopes Marenco, J. Wagler, A. combinatorial equivalence polyhedral combinatorics Point-to-Multipoint systems are one kind of radio systems supplying wireless access to voice/data communication networks. Capacity constraints typically force the reuse of frequencies but, on the other hand, no interference must be caused thereby. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-Hard, and there exist no polynomial time algorithms with a guaranteed quality. In order to apply cutting plane methods to this problem, the associated chromatic scheduling polytopes must be studied. These polytopes have interesting theoretical properties. In this work, we present a characterization of the extreme points of chromatic scheduling polytopes, which enables to prove combinatorial equivalence properties. © 2005 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_15710653_v18_n_p177_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 combinatorial equivalence
polyhedral combinatorics
spellingShingle combinatorial equivalence
polyhedral combinatorics
Marenco, J.
Wagler, A.
Combinatorial equivalence of Chromatic Scheduling Polytopes
topic_facet combinatorial equivalence
polyhedral combinatorics
description Point-to-Multipoint systems are one kind of radio systems supplying wireless access to voice/data communication networks. Capacity constraints typically force the reuse of frequencies but, on the other hand, no interference must be caused thereby. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-Hard, and there exist no polynomial time algorithms with a guaranteed quality. In order to apply cutting plane methods to this problem, the associated chromatic scheduling polytopes must be studied. These polytopes have interesting theoretical properties. In this work, we present a characterization of the extreme points of chromatic scheduling polytopes, which enables to prove combinatorial equivalence properties. © 2005 Elsevier B.V. All rights reserved.
format JOUR
author Marenco, J.
Wagler, A.
author_facet Marenco, J.
Wagler, A.
author_sort Marenco, J.
title Combinatorial equivalence of Chromatic Scheduling Polytopes
title_short Combinatorial equivalence of Chromatic Scheduling Polytopes
title_full Combinatorial equivalence of Chromatic Scheduling Polytopes
title_fullStr Combinatorial equivalence of Chromatic Scheduling Polytopes
title_full_unstemmed Combinatorial equivalence of Chromatic Scheduling Polytopes
title_sort combinatorial equivalence of chromatic scheduling polytopes
url http://hdl.handle.net/20.500.12110/paper_15710653_v18_n_p177_Marenco
work_keys_str_mv AT marencoj combinatorialequivalenceofchromaticschedulingpolytopes
AT waglera combinatorialequivalenceofchromaticschedulingpolytopes
_version_ 1807318489218678784

Ejemplares similares