Catálogo de publicaciones - tesis

Compartir en
redes sociales

Título de Acceso Abierto

Estudios poliedrales de problemas de coloreo de grafos

Diego Andrés Delle Donne Javier Marenco

publishedVersion.

Resumen/Descripción – provisto por el repositorio digital
Los problemas de coloreo de vértices surgen en una amplia gama de situaciones de la vida real. Ejemplos de ellos son los problemas de asignación de frecuencias en redes de telecomunicaciones, problemas de asignación de aulas a las materias de una universidad e incluso algunos problemas de planificación (scheduling). En general, cualquier problema de asignación de recursos a tareas que contemple incompatibilidades entre pares de tareas para usar el mismo recurso, puede ser visto como un problema de coloreo de los vértices de un grafo. Existen muchas variantes de problemas de coloreo de grafos motivadas generalmente por restricciones reales, tales como Precoloring extension, μ-coloring, (γ, μ)-coloring y List-coloring, entre otras. La programación lineal entera (PLE) ha demostrado ser una herramienta muy adecuada para resolver problemas de optimización combinatoria. En los últimos 15 a˜nos la PLE fue aplicada con éxito a problemas de coloreo de vértices recurriendo a distintas formulaciones para el problema clásico de coloreo tales como el modelo estándar, la formulación por representantes, el orientation model y la formulación por conjuntos independientes, entre otras. Si bien muchos problemas de coloreo de grafos pueden ser resueltos en tiempo polinomial en ciertas familias de grafos, la mayoría de estos problemas no está “bajo control” desde el punto de vista poliedral. Es decir, no se conocen formulaciones de programación lineal entera con descripciones completas de los poliedros asociados. En el contexto de la teoría poliedral, la equivalencia entre los problemas de optimización y separación sugiere que para estos problemas debería existir alguna formulación cuyo problema de separación asociado pueda ser resuelto en tiempo polinomial y, más aun, tal que el poliedro asociado admita una caracterización “elegante”, en términos de desigualdades lineales. La búsqueda de tales caracterizaciones es el objetivo principal del presente trabajo de tesis. El objetivo teórico es completar la contraparte poliedral de aquellos problemas de coloreo de grafos que se encuentren ya bien resueltos por medio de técnicas combinatorias. El estudio de estos poliedros puede llevarnos a un mejor entendimiento de sus estructuras permitiéndonos de esta forma encontrar nuevas familias de grafos para las cuales algunos problemas de coloreo tengan resoluci ón polinomial, aportando así nuevos resultados útiles en la práctica. De este estudio surgen también nuevas familias de desigualdades válidas que pueden incorporarse a algoritmos de planos de corte para contribuir así a mejorar su performance en la práctica. Con estos objetivos, en esta tesis estudiamos los poliedros asociados a cuatro formulaciones distintas para el problema clásico de coloreo: el modelo estándar, la formulación por representantes, el orientation model y la formulación por conjuntos independientes. Presentamos adaptaciones de algunas de estas formulaciones para distintas variantes de coloreo y en algunos casos mostramos que los problemas de optimización en los poliedros asociados son polinomialmente equivalentes al problema de optimización sobre el poliedro de coloreo clásico. Damos caracterizaciones completas de los poliedros de coloreo para grafos que surgen de ciertas operaciones. Para algunas de las formulaciones estudiadas, hallamos descripciones completas de los poliedros asociados a distintas familias de grafos, entre ellas los árboles, grafos block, split y co-interval, entre otras. Estudiamos también la relaci ón entre los poliedros de coloreo Pcol y el poliedro de conjuntos independientes STAB y mostramos que en algunos casos, el primero es una cara del segundo (o hasta coincide con éste) para un grafo asociado al grafo original. Estos resultados nos permiten obtener nuevas familias de desigualdades válidas para Pcol basadas en desigualdades válidas conocidas para STAB. Más aun, a raíz de estos resultados hallamos descripciones completas de Pcol para algunas familias de grafos en las que se conoce una descripción de STAB para el grafo asociado. Presentamos también un estudio poliedral clásico para el orientation model en el cual describimos algunas familias de desigualdades válidas que definen facetas del poliedro asociado. Basados en la estructura de estas familias, presentamos el procedimiento de path lifting, que combina dos desigualdades válidas genéricas y un camino entre dos vértices particulares y genera una familia infinita de desigualdades válidas. Mostramos que este procedimiento puede generar facetas del poliedro de coloreo asociado y damos condiciones suficientes para que esto ocurra.
Palabras clave – provistas por el repositorio digital

No disponibles.

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No requiere 2016 Biblioteca Digital (FCEN-UBA) (SNRD) acceso abierto

Información

Tipo de recurso:

tesis

Idiomas de la publicación

  • español castellano

País de edición

Argentina

Fecha de publicación

Información sobre licencias CC

https://creativecommons.org/licenses/by/2.5/ar/