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.
Los problemas de empaquetamiento se busca 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 de servicios (contenedores de basura, cámaras de seguridad, etc.).
La mayoría de estos problemas son NP-difíciles desde el punto de vista de la complejidad computacional. Sin embargo, el enfoque en términos de grafos ha sido de gran importancia para su estudio y ha contribuido al diseño y mejora de algoritmos específicos de resolución.
Habitualmente, distintas aplicaciones imponen restricciones adicionales, surgiendo de esta manera diferentes variaciones de estos problemas.
En este proyecto nos enfocaremos 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 abordaje -desde el punto de vista de la complejidad computacional- de nuevas instancias donde estos problemas sean tratables (resolubles en tiempo polinomial), como así también en la búsqueda de algoritmos de aproximación para instancias donde no lo sean. Para cumplir estos objetivos, haremos uso de técnicas y herramientas que proporcionan las teorías de grafos y de complejidad computacional de problemas de optimización y/o decisión.
