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
Convocatoria Becas ALEARG 2024 para Estudiantes de Ingenierí…
01-07-2024 Gacetillas
Hasta el 31 de julio permanecerá abierta la convocatoria a las becas que ofrece la Secretaría de Educación de la República Argentina y el Servicio Alemán de Intercambio Académico (DAAD) a través del Programa ALEARG, a estudiantes de ingeniería argentinos/as...
Seguir LeyendoApertura convocatoria a las 31º Jornadas de Jóvenes Investi…
08-08-2024 Gacetillas
La Asociación de Universidades Grupo Montevideo informa que se encuentra abierta la convocatoria para presentar trabajos de investigación en el marco de las 31º JORNADAS DE JÓVENES INVESTIGADORES de la Asociación de Universidades Grupo Montevideo (AUGM), a realizarse en la...
Seguir LeyendoEncuentro: ¿Qué vemos a través de los procesos de evaluación…
15-04-2024 Gacetillas
Este espacio que se desarrollará en dos encuentros los días 25/6 y 2/7 de 14 a 16 horas en la sede Pellegrini 250 de la FCEIA, busca identificar las principales dificultades y obstáculos que se presentan en los aprendizajes y...
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 LeyendoConvocatoria Becas ALEARG 2024 para Estudiantes de Ingeniería
Hasta el 31 de julio permanecerá abierta la convocatoria a las becas que ofrece la Secretaría de Educación de la República Argentina y el Servicio Alemán de Intercambio Académico (DAAD) a través del Programa ALEARG, a estudiantes de ingeniería argentinos/as para la realización de una pasantía académica y profesional en Alemania durante un año. En esta convocatoria se concederán 7 becas para todo el país.
Apertura convocatoria a las 31º Jornadas de Jóvenes Investigadores de AUGM
La Asociación de Universidades Grupo Montevideo informa que se encuentra abierta la convocatoria para presentar trabajos de investigación en el marco de las 31º JORNADAS DE JÓVENES INVESTIGADORES de la Asociación de Universidades Grupo Montevideo (AUGM), a realizarse en la Universidad de la República – UdelaR, Montevideo, Uruguay.
Encuentro: ¿Qué vemos a través de los procesos de evaluación?
Este espacio que se desarrollará en dos encuentros los días 25/6 y 2/7 de 14 a 16 horas en la sede Pellegrini 250 de la FCEIA, busca identificar las principales dificultades y obstáculos que se presentan en los aprendizajes y en la enseñanza en los primeros años, tomando como referencia de abordaje las instancias de evaluación.