Buenas estudiantes,
En la clase 5 hemos estudiado la existencia de algoritmos de aproximación para el TSP y para el problema de Steiner.
- Vimos que el problema de Steiner admite una reducción que preserva el factor de aproximación a su versión métrica.
- Luego vimos un algoritmo de aproximación de factor 2 para el problema de Steiner métrico.
- Queda como ejercicio completar los detalles del algoritmo (algoritmo que permite construir un circuito euleriano, optimalidad de Kruskal, algoritmo Atajos y prueba que cada uno de tales algoritmos es polinomial).
- Probamos que el TSP no admite aproximabilidad por ningún algoritmo de tiempo polinomial a menos que P=NP.
- Vimos un algoritmo de factor 2 para el TSP métrico (cuando los costos de las aristas cumplen la desigualdad triangular).
- Vimos el algoritmo de Christofides, que produce un factor 3/2 para el TSP métrico.
- Queda como ejercicio completar los detalles de implementación del algoritmo de Christofides (se pueden reutilizar los algoritmos del ejercicio anterior, e incluir el algoritmo de Edmonds para construir emparejamientos perfectos de mínimo costo).
Cordiales saludos,
Pablo.