«Este es un resultado que he querido toda mi carrera», dijo David Williamson de la Universidad de Cornell, quien ha estado estudiando el problema de los vendedores ambulantes desde la década de 1980.
el problema de los vendedores ambulantes es uno de un puñado de problemas fundamentales a los que los científicos informáticos teóricos recurren una y otra vez para probar los límites de la computación eficiente. El nuevo resultado «es el primer paso para demostrar que las fronteras de la computación eficiente son de hecho mejores de lo que pensábamos», dijo Williamson.,
progreso fraccionario
Si bien probablemente no hay un método eficiente que siempre encuentre el viaje más corto, es posible encontrar algo casi tan bueno: el árbol más corto que conecta todas las ciudades, lo que significa una red de conexiones (o «bordes») sin bucles cerrados. El algoritmo de Christofides utiliza este árbol como columna vertebral para un viaje de ida y vuelta, agregando bordes adicionales para convertirlo en un viaje de ida y vuelta.
cualquier ruta de ida y vuelta debe tener un número par de bordes en cada ciudad, ya que cada llegada es seguida por una salida., Resulta que lo contrario también es cierto: si cada ciudad en una red tiene un número par de conexiones, entonces los bordes de la red deben rastrear un viaje de ida y vuelta.
el árbol más corto que conecta todas las ciudades carece de esta propiedad de uniformidad, ya que cualquier ciudad al final de una rama tiene solo una conexión a otra ciudad. Así que para convertir el árbol más corto en un viaje de ida y vuelta, Christofides (que murió el año pasado) encontró la mejor manera de conectar pares de ciudades que tienen números impares de bordes. Luego demostró que el viaje de ida y vuelta resultante nunca será más del 50% más largo que el mejor viaje de ida y vuelta posible.,
al hacerlo, ideó quizás el algoritmo de aproximación más famoso en Ciencias de la computación teórica, uno que generalmente forma el primer ejemplo en libros de texto y cursos.
«Todo el mundo conoce el algoritmo simple», dijo Alantha Newman de la Universidad de Grenoble Alpes y el Centro Nacional de Investigación Científica de Francia. Y cuando lo sabes, ella dijo, » conoces el estado de la técnica — – al menos, lo hiciste hasta el pasado mes de julio.
Los científicos de la computación han sospechado durante mucho tiempo que debería haber un algoritmo de aproximación que supere al algoritmo de Christofides., Después de todo, su algoritmo simple e intuitivo no siempre es una forma tan efectiva de diseñar una ruta de vendedor ambulante, ya que el árbol más corto que conecta las ciudades puede no ser la mejor columna vertebral que pueda elegir. Por ejemplo, si este árbol tiene muchas ramas, cada ciudad al final de una rama tendrá que ser emparejado con otra ciudad, potencialmente formando un montón de nuevas conexiones costosas.,
En 2010, Oveis Gharan, Saberi y Mohit Singh del Instituto de tecnología de Georgia comenzaron a preguntarse si sería posible mejorar el algoritmo de Christofides eligiendo no el árbol más corto que conecta todas las ciudades, sino un árbol Aleatorio de una colección cuidadosamente elegida. Se inspiraron en una versión alternativa del problema de los vendedores ambulantes en la que se le permite viajar a lo largo de una combinación de caminos, tal vez llegue a Denver a través de 3/4 de la ruta de Chicago a Denver más 1/4 de la ruta de Los Ángeles a Denver.,
a diferencia del problema del vendedor que viaja regular, este problema fraccionario se puede resolver eficientemente. Y si bien las rutas fraccionadas no tienen sentido físico, los científicos de la computación han creído durante mucho tiempo que la mejor ruta fraccionada debería ser una guía aproximada de los contornos de las buenas rutas ordinarias.
así que para crear su algoritmo, Oveis Gharan, Saberi y Singh definieron un proceso aleatorio que recoge un árbol que conecta todas las ciudades, de modo que la probabilidad de que un borde dado esté en el árbol es igual a la fracción de ese borde en la mejor ruta fraccional., Hay muchos de estos procesos aleatorios, por lo que los investigadores eligieron uno que tiende a producir árboles con muchas ciudades conectadas uniformemente. Después de que este proceso aleatorio escupe un árbol específico, su algoritmo lo conecta al esquema de Christofides para emparejar ciudades con números impares de bordes, para convertirlo en un viaje de ida y vuelta.
este método parecía prometedor, no solo para los tres investigadores, sino para otros científicos de la computación. «La intuición es simple», dijo Ola Svensson del Instituto Federal Suizo de tecnología de Lausana. Pero » para demostrarlo resulta ser una bestia diferente.,»
al año siguiente, sin embargo, Oveis Gharan, Saberi y Singh lograron demostrar que su algoritmo supera al algoritmo de Christofides para problemas «gráficos» de vendedores ambulantes, en los que las distancias entre las ciudades están representadas por una red (no necesariamente incluyendo todas las conexiones) en la que cada borde tiene la misma longitud. Pero los investigadores no pudieron averiguar cómo extender su resultado al problema general de los vendedores ambulantes, en el que algunos bordes pueden ser mucho más largos que otros.,
«Si tenemos que añadir una ventaja Super cara a la coincidencia, entonces estamos jodidos, básicamente», dijo Karlin.
empujando hacia atrás
Sin embargo, Oveis Gharan surgió de esa colaboración con una creencia inquebrantable de que su algoritmo debería vencer al algoritmo de Christofides para el problema general de los vendedores ambulantes. «Nunca tuve una duda», dijo.
Oveis Gharan mantiene la vuelta al problema en su mente durante los años que siguieron., Sospechaba que una disciplina matemática llamada geometría de polinomios, poco conocida en el mundo teórico de la informática, podría tener las herramientas que necesitaba. Así que cuando Karlin vino a él hace dos años sugiriendo que co-aconsejaran a un brillante estudiante de posgrado llamado Nathan Klein que había doble especialización en matemáticas y violonchelo, dijo: «OK, vamos a intentarlo — tengo este interesante problema.»
Karlin pensó que, si nada más, sería una oportunidad divertida para aprender más sobre la geometría de los polinomios., «Realmente no pensé que seríamos capaces de resolver este problema», dijo.
ella y Oveis Gharan no dudaron en lanzar a Klein al extremo profundo de la investigación en Ciencias de la computación. Oveis Gharan se había cortado los dientes en el problema de los vendedores ambulantes como estudiante de posgrado en 2010. Y los dos asesores coincidieron en los méritos de asignar problemas difíciles a los estudiantes graduados, especialmente durante sus primeros años, cuando no están bajo presión para obtener resultados.
los tres se sumergieron en una intensa colaboración., «Es todo en lo que estuve pensando durante dos años», dijo Klein.
pasaron el primer año resolviendo una versión simplificada del problema, para tener una idea de los desafíos que enfrentaban. Pero incluso después de que lograron eso, el caso general todavía se sentía como un «disparo de luna», dijo Klein.
aún así, habían tenido una idea de sus herramientas, en particular, la geometría de los polinomios. Un polinomio es una combinación de términos hechos de números y variables elevadas a potencias, como 3x2y + 8xz7., Para estudiar el problema de los vendedores ambulantes, los investigadores destilaron un mapa de ciudades a un polinomio que tenía una variable para cada borde entre las ciudades, y un término para cada árbol que podría conectar todas las ciudades. Los factores numéricos ponderaron estos términos para reflejar el valor de cada borde en la solución fraccionada al problema del vendedor ambulante.
este polinomio, encontraron, tiene una propiedad codiciada llamada «estabilidad real», lo que significa que los números complejos que hacen que el polinomio evalúe a cero nunca se encuentran en la mitad superior del plano complejo., Lo bueno de la estabilidad real es que permanece en vigor incluso cuando haces muchos tipos de cambios en tu polinomio. Así, por ejemplo, si los investigadores quisieran enfocarse en ciudades particulares, podrían usar una sola variable para representar todos los bordes diferentes que conducen a una ciudad, y podrían establecer las variables para bordes que no les importaban igual a 1. A medida que manipulaban estos polinomios simplificados, los resultados de sus manipulaciones aún tenían una estabilidad real, abriendo la puerta a una amplia variedad de técnicas.,
este enfoque permitió a los investigadores manejar preguntas como la frecuencia con la que el algoritmo se vería obligado a conectar dos ciudades distantes. En un análisis de casi 80 páginas, lograron mostrar que el algoritmo supera al algoritmo de Christofides para el problema general de los vendedores ambulantes (el documento aún no ha sido revisado por pares, pero los expertos confían en que sea correcto). Una vez que se completó el documento, Oveis Gharan envió un correo electrónico a Saberi, su antiguo asesor doctoral. «Supongo que finalmente puedo graduarme», bromeó.
