Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto

Marenco, Javier L.

Registro:

Documento:	Tesis Doctoral
Disciplina:	computacion
Título:	Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto
Título alternativo:	Chromatic scheduling polytopes coming from the bandwidth allocation problem in point to multipoint radio access systems
Autor:	Marenco, Javier L.
Editor:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Publicación en la Web:	2012-06-04
Fecha de defensa:	2005
Fecha en portada:	2005
Grado Obtenido:	Doctorado
Título Obtenido:	Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación
Director:	Grötschel, Martín; Annegret, Wagler
Jurado:	Cornuejols, G.; Mundez Diaz. I.; Nasini, G.
Idioma:	Inglés
Palabras clave:	ASIGNACION DE FRECUENCIAS; COMBINATORIA POLIEDRALBANDWIDTH ALLOCATION; POLYHEDRAL COMBINATORICS
Tema:	computación/redes computación/comunicación
Formato:	PDF
Handle:	http://hdl.handle.net/20.500.12110/tesis_n3788_Marenco
PDF:	https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n3788_Marenco.pdf
Registro:	https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n3788_Marenco
Ubicación:	Dep.COM 003788
Derechos de Acceso:	Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Marenco, Javier L.. (2005). Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n3788_Marenco

Resumen:

Lo sistemas de radio punto a multipunto son conjuntos de antenas de radio que proveen acceso inalámbrico a redes de comunicación de voz y datos. Este tipo de sistemas debe ser operado utilizando un cierto espectro de frecuencia de radio, lo cual normalmente produce problemas de capacidad. Por lo tanto es necesario reutilizar frecuencias, pero este reuso no debe generar interferencia entre las señales. El problema de determinar las frecuencias para los enlaces se conoce como el problema de asignación de frecuencias, y en este tipo de sistemas es un caso especial de los problemas de planificación cromática. Estos problemas son NP-hard, y no existen algoritmos aproximados polinomiales con una garantía de calidad fija. Como los métodos de planos de corte han demostrado ser efectivos para muchos otros problemas de optimización combinatoria, el objetivo es aplicar estos métodos al problema de asignación de frecuencias en sistemas punto a multipunto. Para esto, es necesario estudiar previamente los politopos asociados con el problema. El presente trabajo contribuye a este estudio. Introducimos una formulación del problema de asignación de frecuencias en sistemas punto a multipunto como un problema de programación lineal entera, y definimos los politipos de planificación cromática asociados a esta formulación. Estudiamos en primer lugar la estructura combinatoria de estos politipos, analizando los distintos estados - vacuidad, no vacuidad pero dimensión incompleta, dimensión completa pero inestabilidad combinatoria, y estabilidad combinatoria - a medida que el ancho de banda disponible aumenta. Por otra parte, exploramos las relaciones de los politipos de planificación cromática con el politipo de ordenamiento lineal. Desde el punto de vista geométrico, los politipos de planificación cromática son de un interés particular debido a su simetría. como consecuencia de esta propiedad, desarrollamos una importante herramienta para identificar desigualdades que definen facetas sin requerir información sobre la dimensión del politipo. Esto nos permite identificar las restricciones del modelo de programación lineal entera que definen facetas del politipo asociado. Las restantes restricciones del modelo deben ser reforzadas mediante estructuras basadas en cliques del grafo de interferencia para obtener desigualdades que definen facetas. En particular, las desigualdades de clique en cubrimiento generan una gran familia de facetas, y además presentamos varias clases de facetas que provienen de generalizaciones y variaciones de estas desigualdades. Introducimos clases adicionales de facetas basadas en distintos conceptos, y estudiamos la complejidad de los problemas de separación asociados.

Citación:

---------- APA ----------

Marenco, Javier L.. (2005). Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n3788_Marenco

---------- CHICAGO ----------

Marenco, Javier L.. "Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2005.https://hdl.handle.net/20.500.12110/tesis_n3788_Marenco

Estadísticas:

Descargas totales desde :

Navegar

Colección

Tesis Doctoral