He estado mirando este sitio y dice que la gente encontró soluciones para recorridos TSP que son solo 0.031% más altos que el recorrido óptimo. Sin encontrar el recorrido óptimo, ¿cómo saben qué longitud se supone que debe ser?
complexity-theory
approximation
Ilya Gazman
fuente
fuente
Respuestas:
En general, cuando desea vincular la relación de aproximación de un algoritmo, busca un límite inferior fácil en el valor óptimo. Lo más sencillo es a menudo la relajación LP de una formulación ILP (adecuadamente elegida) del problema. A veces se usan otras cosas, por ejemplo, para TSP también puede usar el peso de un MST (el recorrido óptimo menos un borde es un árbol, por lo que no puede pesar menos que el MST).
Para casos particulares, por supuesto, todavía puede usar lo que usa en sus pruebas, es decir, puede resolver el LP y comparar su solución heurística con el valor del LP. Si tiene más tiempo de CPU en sus manos, también puede iniciar un proceso de bifurcación para resolver el ILP. Incluso si no resuelve el ILP por completo, obtendrá mejores límites inferiores de la dualidad LP.
fuente