Los problemas de empaquetamiento y el cubrimiento de conjuntos son dos conceptos duales fundamentales en optimización combinatoria, los cuales son equivalentes a través de transformaciones apropiadas. Estos problemas son relevantes en la práctica, pero difíciles de resolver en general. Una manera a menudo exitosa de resolver esta clase de problemas es el enfoque poliedral relativo al espacio de soluciones del problema. En este proyecto en particular, abordamos aplicaciones del problema de cubrimiento de conjuntos que provienen del problema de dominación en grafos y sus variantes. En particular se estudiarán los siguientes temas: TEMA 1: Problema de dominación en grafos redes. Numerosas aplicaciones pueden ser modeladas como problemas de dominación en grafos (ver Henning (1997)). El problema de dominación clásico en un grafo es el problema de hallar un conjunto dominante de cardinal mínimo, es decir, un subconjunto de vértices de cardinal mínimo que tenga intersección no vacía con las vecindades cerradas del grafo. Este problema admite una formulación en términos del problema de cubrimiento de conjuntos. El enfoque poliedral ha sido de gran importancia para la resolución del problema y ha contribuido a la construcción y mejora de algoritmos específicos de resolución de algunas instancias. En particular, el problema de dominación en grafos redes se traduce en el problema de cubrimiento sobre matrices circulantes. TEMA 2: Problema de códigos de identificación en grafos. Habitualmente, las distintas aplicaciones que se modelan como problemas de dominación en grafos, imponen restricciones adicionales a los conjuntos dominantes, surgiendo de esta manera variaciones del problema (ver Henning (1997)). En efecto, a partir del concepto de dominación en grafos se modelan entre otros, problemas de locación de servicios (contenedores de residuos domiciliarios, hospitales, estaciones de bomberos, cajeros automáticos, etc.). Ejemplos clásicos son la detección de incendios en edificios y la detección de fallas en redes de procesadores. En estos casos se necesita instalar detectores de incendio o de fallas en ciertos lugares. Los detectores son suficientemente potentes como para detectar el problema incluso en los sitios contiguos a los lugares en donde se encuentran, por lo tanto se pretende instalar la menor cantidad de detectores posibles de manera que a partir del conjunto de detectores que dieron la alarma, se pueda identificar el sitio exacto en donde se ha producido la amenaza. Este conjunto de detectores es lo que se conoce como un código de identificación y el problema de cubrimiento de conjuntos también permite la formulación del problema de mínimo código de identificación como un programa entero.
Novedades
JONICA 2024
15-04-2024 Gacetillas
El 30 de mayo se llevará a cabo una nueva edición de las JONICA (Jornadas de Ingeniería Electrónica) organizada por la Escuela de Ingeniería Electrónica de la FCEIA.
Seguir LeyendoMateliga 2024
12-04-2024 Gacetillas
El próximo 18 de mayo se realizará una nueva edición de Mateliga, una competencia de matemática por equipos para estudiantes de escuelas secundarias organizada por el Departamento de Matemática de la Escuela de Ciencias Exactas y Naturales de la FCEIA.
Seguir LeyendoConvocatoria Programa MARCA 2024 para estudiantes de Civil
09-04-2024 Gacetillas
En el marco del Proyecto “Formación de ingenieros civiles comprometidos con el desarrollo sostenible: la agenda 2030 y los ODS como meta”, aprobado en la 12° Convocatoria del Programa MARCA MERCOSUR, se convoca a estudiantes de Ingeniería Civil para realizar...
Seguir LeyendoConvocatoria Programa MARCA para estudiantes de Mecánica
08-04-2024 Gacetillas
MARCA es el primer programa de movilidad de estudiantes de grado promovido por los gobiernos de Argentina, Bolivia, Brasil, Paraguay y Uruguay, desde el Sector Educativo del MERCOSUR. La movilidad se realiza entre los países del MERCOSUR y se desarrolla...
Seguir LeyendoXV Edición del Programa para el Fortalecimiento de la Funció…
25-03-2024 Gacetillas
La Fundación Botín lanza la XV edición del Programa para el Fortalecimiento de la Función Pública en América Latina que se desarrollará de octubre a noviembre 2024, con el objetivo de impulsar el desarrollo de la región por medio de...
Seguir LeyendoPrograma Jóvenes Líderes Iberoamericanos 2024 para graduados…
25-03-2024 Gacetillas
La Fundación Carolina y Banco Santander convocan el Programa Jóvenes Líderes Iberoamericanos, cuya 19ª edición tendrá lugar del 23 de junio al 05 de julio de 2024, en Madrid, Barcelona y Bruselas.
Seguir LeyendoEventos de Extensión 2024
19-03-2024 Gacetillas
Compartimos información sobre dos eventos de extensión que se desarrollarán durante 2024.
Seguir LeyendoJONICA 2024
El 30 de mayo se llevará a cabo una nueva edición de las JONICA (Jornadas de Ingeniería Electrónica) organizada por la Escuela de Ingeniería Electrónica de la FCEIA.
Mateliga 2024
El próximo 18 de mayo se realizará una nueva edición de Mateliga, una competencia de matemática por equipos para estudiantes de escuelas secundarias organizada por el Departamento de Matemática de la Escuela de Ciencias Exactas y Naturales de la FCEIA.
Convocatoria Programa MARCA 2024 para estudiantes de Civil
En el marco del Proyecto “Formación de ingenieros civiles comprometidos con el desarrollo sostenible: la agenda 2030 y los ODS como meta”, aprobado en la 12° Convocatoria del Programa MARCA MERCOSUR, se convoca a estudiantes de Ingeniería Civil para realizar una movilidad semestral en la Universidad Federal de Pernambuco, Recife, Brasil.