Estudio poliedral del problema de coloreo acíclico

Braga, Mónica Andrea

Repositorio UNGS
→
ICI - Producción académica del Instituto de Ciencias
→
Tesis de posgrado
→
Ver ítem

dc.contributor	Marenco, Javier
dc.creator	Braga, Mónica Andrea
dc.date.accessioned	2019-06-03T20:10:13Z
dc.date.available	2019-06-03T20:10:13Z
dc.date.issued	2015
dc.identifier.uri	http://repositorio.ungs.edu.ar/handle/UNGS/256
dc.description	Un coloreo de un grafo es una asignación de colores a sus vértices de modo tal que todo par de vértices adyacentes recibe colores distintos. Un coloreo acíclico de un grafo es un coloreo tal que ningún ciclo del grafo recibe exactamente dos colores, y el número cromático acíclico XA(G)de un grafo G se define como el número mínimo de colores necesarios para garantizar la existencia de un coloreo acíclico de G. Dado un grafo G, el problema de coloreo acíclico consiste en hallar un coloreo acíclico de G con XA(G) colores. Este problema surge en el contexto de la implementación de algoritmos eficientes para el cálculo de matrices Hessianas poco densas y simétricas a través de métodos de sustitución. Dado un grafo G y un entero k, el problema de determinar si XA(G) <= k es un problema NPcompleto, con lo cual no se conocen algoritmos eficientes (es decir, polinomiales en el tamaño de G) para este problema. En particular, el problema de determinar si XA(G) <= 3 es NP-completo.Una técnica que suele ser exitosa para la resolución computacional de problemas de optimización combinatoria es el planteo de algoritmos basados en planos de corte, sobre la base de una formulación del problema como un modelo de programación lineal entera. Este enfoque involucra el estudio de la cápsula convexa de las soluciones factibles del modelo planteado, buscando familias de desigualdades válidas que puedan ser incorporadas en un algoritmo de este tipo. Dado que este enfoque resultó útil para muchos otros problemas, en esta tesis se comienza este estudio para el problema de coloreo acíclico.En esta tesis se introduce un modelo de programación lineal entera para el problema de coloreo acíclico y se estudian sus propiedades. Se analiza la dimensión de la cápsula convexa de las soluciones factibles y, sobre esta base, se estudian desigualdades válidas y se analizan sus propiedades. Se presentan familias de desigualdades válidas basadas en ciclos y cliques del grafo, y se prueba bajo qué condiciones estas desigualdades definen facetas del poliedro cápsula convexa asociado con la formulación. Se muestra que todas las desigualdades presentadas en este trabajo definen facetas bajo condiciones generales.Se estudia además el rango disyuntivo de las familias de desigualdades presentadas en este trabajo, asociado al operador BCC definido por Balas, Ceria y Cornuéjols. Se propone en esta tesis un concepto complementario al de rango disyuntivo, llamado anti-rango disyuntivo de una desigualdad válida. Este parámetro es de interés como medida teórica de la calidad de la desigualdad, y se estudian los anti-rangos disyuntivos de las desigualdades presentadas en este trabajo.
dc.description	Fil: Braga, Mónica Andrea. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina.
dc.format	application/pdf
dc.format.extent	99 p.
dc.language.iso	spa
dc.publisher	Universidad Nacional de General Sarmiento
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	https://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subject	CONCEPTOS MATEMATICOS
dc.subject	MODELOS MATEMATICOS
dc.subject	PROGRAMACION
dc.subject	COMPUTACION
dc.title	Estudio poliedral del problema de coloreo acíclico
dc.type	info:eu-repo/semantics/doctoralThesis
dc.type	info:ar-repo/semantics/tesis doctoral
dc.type	info:eu-repo/semantics/acceptedVersion