Problemas de empaquetamiento y cubrimiento en grafos. Parte 2

Dra. Valeria Leoni
valeoni@fceia.unr.edu.ar

Este proyecto se presenta como una continuidad por dos años (2018-2020) del 1ING504 (2016-2018), con los mismos integrantes internos (de la UNR) al que se suman ahora nuevos colaboradores externos con los cuales se generaron vínculos que se pretende se fortalezcan en el transcurso de esta segunda etapa. Recordamos que los problemas de empaquetamiento y cubrimiento en grafos y las interrelaciones entre ellos pertenecen a los tópicos fundamentales en Optimización Combinatoria y Teoría de Grafos, con un amplio espectro de aplicación en Ciencias de la Computación, Investigación Operativa y muchos otros campos. Por un lado, los problemas de empaquetamiento se preguntan sobre una colección máxima de objetos que no estén en conflicto, mientras que los problemas de cubrimiento lo hacen sobre una colección mínima de objetos que cubren ciertas estructuras. Numerosas aplicaciones pueden ser modeladas como problemas de empaquetamiento y cubrimiento en grafos; entre otros, problemas de ubicación y/o asignación de servicios (contenedores de basura, cámaras de seguridad, vehículos de repartos, entre otros). La mayoría de estos problemas de optimización y/o decisión son NP-difíciles desde el punto de vista de la complejidad computacional. Sin embargo, el enfoque matemático ha sido de gran importancia para su estudio y ha contribuido al diseño y mejora de algoritmos específicos de resolución. Habitualmente, cada aplicación específica impone restricciones adicionales, surgiendo de esta manera diferentes variaciones de estos problemas. En este proyecto continuaremos enfocándonos en las variaciones y generalizaciones de los problemas de empaquetamiento y de cubrimiento en grafos, conocidos como problemas de Empaquetamiento Limitado y de Dominación Múltiple. Nuestro estudio se centrará fundamentalmente en el tratamiento de nuevas instancias donde las variaciones -ya definidas por otros autores o por este grupo en la etapa anterior de este proyecto- son tratables, es decir, resolubles en tiempo polinomial. Agregamos a esta segunda etapa del proyecto la definición de nuevas generalizaciones de los problemas existentes, con el objeto de dar un enfoque unificador y a la vez abarcar nuevas aplicaciones reales. Además incorporamos otro tema de estudio (ver Tema 2: Modelos de equilibrio de asignación de transporte privado) que se trabajará en colaboración con el Prof. Ing. Cristian Cortés Carillo y el Dr. Pablo Rey (Universidad de Chile), ambos especialistas en el área, en el marco del trabajo de tesis de posgrado de una de las integrantes del proyecto. Para cumplir estos objetivos, seguiremos haciendo uso de técnicas y herramientas que proporciona las teorías de grafos y de complejidad computacional de problemas de optimización y/o decisión.

 

SASE 2019: concurso para estudiantes

24-04-2019 Gacetillas

Del 17 al 19 de julio se desarrollará en la FCEIA el Simposio Argentino de Sistemas Embebidos 2019 (SASE). Entre sus objetivos el SASE busca fomentar la interacción industria-academia en...

Seguir Leyendo

6º Convocatoria de Proyectos de Vinculación Tecnológica y De…

16-04-2019 Gacetillas

La UNR lanza la 6º Convocatoria a Proyectos de Vinculación Tecnológica y Desarrollo Productivo “Vinculación Inclusiva” 2019. La misma permanecerá abierta hasta el 27 de mayo y se financiarán 20...

Seguir Leyendo
Más novedades

Diego Saikin visitó la FCEIA y contó su experiencia en el proyecto Bereshit

De Argentina a Israel y de Israel a la Luna. El argentino Diego Saikin visitó la FCEIA para contar su experiencia como integrante del equipo israelí SpaceIL, responsable de conceptualizar y crear a Bereshit”, la primera misión privada a la Luna en la historia.

Leer más: Diego Saikin visitó la FCEIA y contó su experiencia en el proyecto Bereshit

¿Cómo influye el cambio generacional en la educación?

Beatriz Salemme Correa Cortela es Doctora y Máster en Educación para la Ciencia y hace algunas semanas visitó la FCEIA para dictar el curso de Posgrado "Desafíos de la docencia en la Enseñanza Superior en el área de Ciencias Exactas y Naturales. Posibles abordajes y enfrentamientos". Durante su estadía en la ciudad compartió sus conocimientos sobre nuevas metodologías de enseñanza y la vinculación que existe entre escuela y universidad.

Leer más: ¿Cómo influye el cambio generacional en la educación?

La FCEIA eligió a sus nuevas autoridades

El lunes 22 de abril se realizó una sesión especial de Consejo Directivo donde los consejeros realizaron la votación para elegir a las próximas autoridades de la FCEIA, siendo electa como Decana la Ingeniería Electricista y Doctora en Educación, Graciela Utges.

Leer más: La FCEIA eligió a sus nuevas autoridades

La experiencia de un graduado en el Heidelberg Laureate Forum

Demian Goos es graduado de la Licenciatura en Matemática de la FCEIA y doctorando de nuestra Universidad. En 2017 participó durante una semana del Heidelberg Laureate Forum, un evento que reúne reconocidos matemáticos con jóvenes investigadores.

Leer más: La experiencia de un graduado en el Heidelberg Laureate Forum

Nodocente de la FCEIA viajó a España para capacitarse

A partir del Programa de Ayuda de Viaje al Extranjero (AVE), Silvia Saabedra, quien se desempeña en el Laboratorio de Informática de la Escuela de Ingeniería Electrónica, viajó a España para realizar tareas de intercambio y capacitación en el desarrollo, funcionamiento y mantenimiento de sistemas informáticos y  redes.

Leer más: Nodocente de la FCEIA viajó a España para capacitarse

Día del investigador científico

Cada 10 de abril se celebra en Argentina el día del Investigador Científico, en homenaje al nacimiento del Dr. Bernardo Houssay (1887-1971).

Leer más: Día del investigador científico

Las Cátedras de Introducción a la Ingeniería se reunirán en Rosario

El 1 de noviembre de 2019 la FCEIA será sede del V Encuentro Nacional de Cátedras de Introducción a la Ingeniería.

Leer más: Las Cátedras de Introducción a la Ingeniería se reunirán en Rosario

Información importante sobre las elecciones estudiantiles 2019

Del 9 al 11 de abril próximo se desarrollarán en la FCEIA las elecciones correspondientes al claustro estudiantil. Los alumnos de la Facultad que se encuentran en el padrón podrán elegir Centro de Estudiantes y sus representantes en el Consejo Directivo de la Facultad.

Leer más: Información importante sobre las elecciones estudiantiles 2019

Reunión Nacional de Educación en Física en la FCEIA

Del 30 de septiembre al 4 de octubre se desarrollará en Rosario la XXI Reunión Nacional de Educación en Física (REF) bajo el lema “El desafió de enseñar Física”.

Leer más: Reunión Nacional de Educación en Física en la FCEIA