28
Jue, Mar

Problemas de empaquetamiento y cubrimiento en grafos. Parte 2

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.