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.

 

Finalizó la especialización en Ciencias de la Computación para docentes primarios

El pasado 3 de julio se realizó el cierre del dictado de la primera cohorte de la "Especialización Docente de Nivel Superior en Didáctica de las Ciencias de la Computación: Aprendizaje y Enseñanza del Pensamiento Computacional y la Programación en el Nivel Primario".

Leer más: Finalizó la especialización en Ciencias de la Computación para docentes primarios

La Escuela de Posgrado comenzará a dictar dos nuevas carreras

La Escuela de Posgrado y Educación Continua (EPEC) de la FCEIA dará inicio, en agosto, al cursado de dos nuevas carreras de especialización: en Infraestructura de Datos Espaciales (IDEs) y en Ingeniería de Petróleo y Gas (PyG).

Leer más: La Escuela de Posgrado comenzará a dictar dos nuevas carreras

Día de la Cartografía, ¿por qué es importante esta ciencia para el desarrollo de las regiones?

El 26 de junio se celebra en Argentina el Día de la Cartografía en homenaje a la fecha de creación del Departamento Topográfico impulsado por Bernardino Rivadavia en 1826. La cartografía es la ciencia que se encarga del estudio y elaboración de la representación gráfica del territorio.

Leer más: Día de la Cartografía, ¿por qué es importante esta ciencia para el desarrollo de las regiones?

Graduado de la FCEIA y becario del IFIR ganó una beca internacional

Martín Toderi, egresado de la Licenciatura en Física y becario del Instituto de Física de Rosario, se convirtió recientemente en el único argentino en obtener una beca internacional que le permitirá continuar con sus investigaciones en el campo de las ópticas innovadoras para el estudio de componentes de la sangre. 

Leer más: Graduado de la FCEIA y becario del IFIR ganó una beca internacional

Tutorías desarrolló la charla “Ingeniería, ambiente y sustentabilidad”

El pasado 5 de junio el Área de Tutorías realizó la actividad “Ingeniería, ambiente y sustentabilidad” en el marco del Día Mundial del Medio Ambiente.

Leer más: Tutorías desarrolló la charla “Ingeniería, ambiente y sustentabilidad”

6 de junio: Día de la Ingeniería

La fecha conmemora la graduación del primer Ingeniero Civil de Argentina, Luis Augusto Huergo.

Leer más: 6 de junio: Día de la Ingeniería

¿Cómo afecta la redefinición del kilogramo y otras unidades de medida?

La Conferencia General de Pesas y Medidas (CGPM) aprobó en noviembre de 2018 la mayor revisión del Sistema Internacional de Unidades (SI) desde su creación en 1960. Se redefinieron cuatro unidades de base: el kilogramo, el ampere, el kelvin y el mol y se reformuló el metro, el segundo y la candela. 

Leer más: ¿Cómo afecta la redefinición del kilogramo y otras unidades de medida?

El Consejo Consultivo de Decanos de Santa Fe se reunió en la FCEIA

Se realizó una nueva reunión del Consejo Consultivo de Decanos de Facultades de Ingeniería de la Provincia de Santa Fe. En esta oportunidad, la sede del encuentro fue la FCEIA.

Leer más: El Consejo Consultivo de Decanos de Santa Fe se reunió en la FCEIA

Asumieron las nuevas autoridades de la FCEIA

El martes 21 de abril se realizó el acto de asunción de las nuevas autoridades para el periodo 2019-2023. La nueva Decana, Dra. Ing. Graciela Utges, y el Vicedecano, Ing. Damián Portaro, fueron elegidos en una sesión especial de Consejo Directivo en abril pasado. 

Leer más: Asumieron las nuevas autoridades de la FCEIA