Defensa Tesis Licenciatura Ernesto Adrián Álvarez Capandeguy, María Fernanda Managó

• Título: "Nueva heurística para el Problema de Recubrimiento de Grafos por Ciclos Acotados"
• Alumnos: Ernesto Adrián Álvarez Capandeguy, María Fernanda Managó
• Directora: Irene Loiseau
• Jurados: Javier Marenco, Francisco Soulignac
• Resumen

El despliegue de enlaces de alta capacidad en redes de telecomunicaciones trajo como consecuencia la necesidad de que grandes redes deban operar sin ninguna falla. Debido al uso de esta clase de enlaces muy pocos transportan la información de gran cantidad de canales, que tradicionalmente dependían de muchos enlaces de menor capacidad. La posibilidad de que un número pequeño de fallas pudiera causar la caída de una red hizo que la creación de enlaces tolerantes a fallos se volviera un tema de mucha importancia. Una técnica para proveer este tipo de robustez a la red es formarla usando Self Healing Rings (SHR). En este trabajo proponemos una heurística para resolver el Bounded Cycle Cover Problem (BCCP), el cual consiste en encontrar un cubrimiento de un grafo 2-conexo con ciclos de costo mínimo y una cantidad acotada de ejes, que puede aplicarse a la creación de SHR tolerantes a fallos. La solución que proponemos es una variante de GRASP, cuya principal diferencia está en el mecanismo de selección de los ciclos candidatos. Mientras que GRASP lista los vecinos más ventajosos según la función greedy, y luego elige uno al azar, nuestra heurística selecciona vecinos al azar y se queda con el más ventajoso de ellos. Nuestro algoritmo, comparado con otras heurísticas que aproximan soluciones para el mismo problema consigue soluciones de mejor calidad, en algunos casos a costa de un mayor tiempo de cómputo.