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
Curso online de francés
21-03-2023 Gacetillas
La Alianza Francesa de Buenos Aires ofrece un curso virtual « Etudier et vivre en France », destinado específicamente a quienes van a ir a estudiar a Francia.
Seguir LeyendoConvocatoria Programa ESCALA Estudiantes de Grado de AUGM
20-03-2023 Gacetillas
Hasta el 2 de mayo permanecerá abierta la convocatoria del Programa ESCALA Estudiantes de Grado de AUGM para movilidades presenciales a realizarse durante el segundo cuatrimestre de 2023.
Seguir LeyendoXIV Convocatoria de la Fundación Botín 2023
20-03-2023 Gacetillas
Hasta el 27 de abril se encuentra abierta la convocatoria a estudiantes de todas las carreras para participar de la XIV edición del Programa para el Fortalecimiento de la Función Pública en América Latina de la Fundación Botín (España) que...
Seguir LeyendoConvocatoria concurso nacional mejor tesis de ingeniería
15-03-2023 Gacetillas
La empresa Invap premiará a las mejores tesis de ingeniería del país. La convocatoria, que permanecerá abierta hasta el 31 de mayo, está destinada a estudiantes universitarios de las carreras de ingeniería industrial, mecánica y electrónica.
Seguir LeyendoCurso “Límites, infinitésimos, aproximaciones. Otra mirada”
09-03-2023 Gacetillas
4 encuentros: 15, 22 y 29 de marzo y 5 de abril
Seguir LeyendoBeca Erasmus + para realizar un intercambio en la Escuela de…
15-02-2023 Gacetillas
Convocatoria abierta 2023-2024
Seguir LeyendoCurso online de francés
La Alianza Francesa de Buenos Aires ofrece un curso virtual « Etudier et vivre en France », destinado específicamente a quienes van a ir a estudiar a Francia.
Convocatoria Programa ESCALA Estudiantes de Grado de AUGM
Hasta el 2 de mayo permanecerá abierta la convocatoria del Programa ESCALA Estudiantes de Grado de AUGM para movilidades presenciales a realizarse durante el segundo cuatrimestre de 2023.
XIV Convocatoria de la Fundación Botín 2023
Hasta el 27 de abril se encuentra abierta la convocatoria a estudiantes de todas las carreras para participar de la XIV edición del Programa para el Fortalecimiento de la Función Pública en América Latina de la Fundación Botín (España) que se desarrollará de octubre a diciembre 2023.