[Todos] Seminario de Optimización y Grafos este jueves

[Flavia Bonomo]

Invitamos a todos al Seminario de Optimización y Grafos, edición 2008, del
grupo de investigación en Teoría de Grafos y Optimización Combinatoria
(http://www.dc.uba.ar/inv/grupos/grafos)
de los departamentos de Computación y Matemática de la FCEN, UBA y el
Instituto de Ciencias de la UNGS.

El seminario es los jueves de 19 a 20.30, y el cronograma preliminar
puede verse en http://www.dc.uba.ar/inv/grupos/grafos/seminario

Los invitamos este jueves 20 de noviembre a una charla doble, desde las
19hs en el Laboratorio 3 (planta baja, pab I). Habra coffe break entre las
dos charlas :)

--------
"Estudio poliedral del problema de coloreo acíclico"

Mónica Braga (Instituto de Ciencias, UNGS)

 y

"Sobre coloreos equitativos"

Clara Betancur (DC, FCEN, UBA)
--------

Resumen de la primera charla:

El problema de coloreo acíclico surge naturalmente en el contexto de la
resolución de problemas de partición de matrices. Muchos algoritmos para
resolver problemas de optimización numérica y sistemas de ecuaciones no
lineales requieren de la estimación de la matriz Jacobiana o Hessiana
asociada a las funciones que participan en el problema. Aprovechando la
estructura poco densa de estas matrices, es posible reducir la cantidad de
evaluaciones de la función en forma significativa. El problema de
minimizar el número de evaluaciones necesarias para estimar una matriz
Hessiana se puede formular como un problema particular de coloreo de
grafos. En esta charla veremos cómo se modela este problema como un
problema de coloreo acíclico, plantearemos un modelo de programación
lineal entera y comenzamos su estudio poliedral.


Resumen de la segunda charla:

La noción de coloreo equitativo fué introducida por Walter Meyer en el año
1973, coloreado que tiene como condición adicional, que la cantidad de
vértices de
cada clase de colores difiera a lo sumo en uno. La motivación provino de
Tucker con el problema de recolección de basura y Meyer pensó que para
este problema
era conveniente tener un número aproximadamente igual de rutas. En este
trabajo presentamos una serie de conceptos fundamentales y los resultados
más recientes,
que muestran el estado del arte sobre el coloreado equitativo de grafos.
El número cromático equitativo, $\chi_=(G)$, es el menor entero k tal que
G es k-coloreado equitativamente. A partir de éste número demostraremos
algunos resultados para ciertos tipos de grafos, mostrando las condiciones
que se requieren para que tengan dicho coloreo.