Los investigadores refutan una creencia generalizada sobre los algoritmos en línea | Revista Quanta

En la vida a veces tenemos que tomar decisiones sin toda la información que queremos; Esto también se aplica a la informática. Este es el ámbito de los algoritmos en línea, que, a pesar de su nombre, no necesariamente involucran Internet. Más bien, se trata de estrategias de resolución de problemas que responden a los datos a medida que llegan, sin ningún conocimiento de lo que podría venir después. Esa capacidad de hacer frente a la incertidumbre hace que estos algoritmos sean útiles para enigmas del mundo real, como administrar la memoria de una computadora portátil o elegir qué anuncios mostrar a las personas que navegan por la web.

Los investigadores estudian versiones generalizadas de estos problemas para investigar nuevos métodos para abordarlos. Entre los más famosos se encuentra el “k-problema del servidor”, que describe la espinosa tarea de enviar una flota de agentes para cumplir con las solicitudes que llegan una por una. Podrían ser técnicos de reparación, bomberos o incluso vendedores ambulantes de helados.

"Es realmente sencillo definir este problema", dijo Marcin Bieńkowski, investigador de algoritmos de la Universidad de Wrocław en Polonia. Pero "resulta ser extrañamente difícil". Desde que los investigadores comenzaron a atacar el k-Problema del servidor a finales de los años 1980, se han preguntado exactamente qué tan bien los algoritmos en línea pueden manejar la tarea.

A lo largo de las décadas, los investigadores comenzaron a creer que siempre se puede lograr un cierto nivel de rendimiento algorítmico para el k-problema del servidor. Entonces, no importa qué versión del problema estés enfrentando, habrá un algoritmo que alcance este objetivo. Pero en un artículo publicado por primera vez en línea en noviembre pasado, tres científicos informáticos mostró que esto no siempre es posible. En algunos casos, todos los algoritmos se quedan cortos.

"Estoy feliz de decir que fue una gran sorpresa para mí", dijo Anupam Gupta, que estudia algoritmos en la Universidad Carnegie Mellon y no participó en el artículo. El trabajo ofrece "una visión más profunda del problema central en esta área".

Primero los informáticos describió este problema en 1988. Para tener una idea, imaginemos una empresa que emplea fontaneros. A medida que llegan las llamadas, la empresa debe decidir qué fontanero va a cada lugar. El objetivo de la empresa (y el objetivo de un algoritmo para la k-problema del servidor: consiste en minimizar la distancia total recorrida por todos los fontaneros.

Lo complicado es que la empresa no sabe de antemano de dónde procederán las llamadas. Si fuera así, entonces podría depender de un “algoritmo fuera de línea” que conozca el futuro. En particular, podría utilizar una estrategia de despacho ideal que encuentre una solución con el menor recorrido total para cualquier cadena de llamadas. Ningún algoritmo en línea podrá superarlo, ni siquiera igualarlo de manera confiable.

Pero los investigadores quieren acercarse lo más posible. Miden el rendimiento de un algoritmo online comparando la distancia recorrida en cada estrategia, calculando lo que se conoce como ratio competitivo. Los diseñadores de algoritmos intentan diseñar estrategias en línea que se acerquen al ideal fuera de línea, reduciendo esta proporción a 1.

Imaginemos que nuestra empresa de plomería tiene solo dos plomeros y solo presta servicio a una calle larga y única. Las llamadas llegan una a la vez. Un primer enfoque razonable, conocido como algoritmo codicioso, sería enviar al fontanero que esté más cerca de la ubicación de cada llamada entrante. Pero aquí hay un escenario en el que este algoritmo tiene problemas: imagine que un plomero comienza en el extremo oeste de la calle y el otro en el extremo este, y todas las llamadas provienen de dos casas vecinas en el extremo oeste. En ese caso, un plomero nunca se mueve mientras el otro acumula kilómetros en esas dos casas. En retrospectiva, la mejor estrategia habría sido trasladar a ambos plomeros al área propensa a problemas, pero, lamentablemente, no se podía saber dónde iba a ser.

Aun así, dijo Bieńkowski, es posible hacerlo mejor que el algoritmo codicioso. El "doble coberturaEl algoritmo mueve a ambos fontaneros al mismo ritmo hacia cualquier llamada que se interponga entre ellos, hasta que uno de ellos llega a ella. Este método logra una relación competitiva más baja que el algoritmo codicioso.

Si bien este problema abstracto no es relevante para las empresas de plomería reales, "el k"El problema del servidor en sí es realmente la cuestión definitoria" en la informática en línea, dijo Yuval Rabani, un científico informático de la Universidad Hebrea de Jerusalén y coautor del artículo reciente. En parte, esto se debe a que las herramientas y técnicas desarrolladas durante el trabajo en el k-Los problemas del servidor suelen encontrar aplicaciones en otras partes del estudio de algoritmos en línea, e incluso fuera de él.

"Esto es parte de la magia de trabajar con algoritmos", dijo.

Cuando estudian estos problemas, a los científicos les gusta imaginarlos como juegos contra un adversario. El adversario elige una secuencia diabólica de solicitudes para hacer que el algoritmo en línea funcione lo peor posible en comparación con su contraparte fuera de línea. Para robarle al adversario parte de su poder, los investigadores utilizan algoritmos que incluyen decisiones aleatorias.

Esta estrategia es bastante eficaz y los investigadores han sospechado desde principios de los años 1990 que siempre es posible encontrar un algoritmo aleatorio que alcance un objetivo de rendimiento específico: una relación competitiva proporcional al log. k, Donde k es el número de agentes. Esto se llama aleatorio. k-Conjetura del servidor, y los investigadores han demostrado que es cierta para algunos espacios o conjuntos específicos de puntos (el equivalente a casas que podrían requerir plomeros). Pero no se ha demostrado en todos los casos.

Como la mayoría de los investigadores, Rabani y sus coautores: Sébastien Bubeck de Microsoft Research y Christian Coester de la Universidad de Oxford) pensó que la conjetura era cierta. "No tenía motivos para dudarlo", dijo Coester.

Pero eso empezó a cambiar cuando trabajaron en otro problema en línea. Tenía conexiones con el k-problema del servidor y el límite inferior conocido de la relación competitiva era inesperadamente alto. Les hizo pensar que tal vez un objetivo tan bajo como el log k para k-El problema del servidor era demasiado optimista.

Rabani dijo que fue Coester quien sugirió por primera vez que el estudio aleatorio k-La conjetura del servidor puede ser falsa. "Tan pronto como lo dijo, todo cobró sentido".

Para refutar la conjetura, los autores jugaron el papel del adversario, creando una tormenta perfecta que impediría que cualquier algoritmo en línea alcanzara una proporción competitiva de log. k. Su estrategia tenía dos partes: construyeron una familia de espacios complejos similares a fractales y diseñaron una distribución de secuencias de solicitudes que sería difícil para cualquier algoritmo posible. En el primer movimiento del algoritmo, la estructura del espacio significaba que tenía que elegir entre dos caminos idénticos, uno de los cuales eventualmente requeriría viajes adicionales según las solicitudes. Luego, los autores utilizaron un método llamado recursividad para construir espacios que multiplicaran estos puntos de decisión, forzando al algoritmo a caer en un amasijo de malas opciones y elevando el costo.

Las elecciones le recordaron a Rabani el poema de Robert Frost “El camino no tomado,” en el que un viajero contempla dos posibles caminos a través de un bosque amarillo. "Simplemente aplicamos el poema de forma recursiva", bromeó. "Y luego las cosas van realmente mal".

Los autores demostraron que, en los espacios que habían construido, un algoritmo aleatorio nunca puede lograr una relación competitiva mejor que (log k)², impulsando un objetivo universal de registro k para siempre fuera de su alcance. Habían refutado la conjetura.

Este trabajo, que ganó un Premio al mejor papel en el 2023 Simposio sobre Teoría de la Computación, marca un hito "sólidamente teórico", dijo Gupta. Este tipo de resultado ayuda a indicar qué tipo de rendimiento podemos esperar de nuestros algoritmos. En la práctica, sin embargo, los diseñadores de algoritmos a menudo no planifican en torno a los peores escenarios, con un adversario omnipotente y una completa ignorancia del futuro. Cuando los algoritmos se aplican a problemas del mundo real, a menudo superan las expectativas teóricas.

El artículo, que también demostró límites para algoritmos aleatorios utilizados para otros problemas, también podría tener implicaciones para futuros trabajos en este campo. El resultado claramente "destaca el poder" de la técnica que utilizaron los autores, dijo Gupta.

Tal vez esos hallazgos futuros desafíen las expectativas de los investigadores como lo hizo éste, dijo Rabani. "Este es uno de los casos en los que se siente realmente bien equivocarse".

¿Cuánto está realizando una serie de encuestas para servir mejor a nuestra audiencia. Toma nuestro encuesta a lectores de informática y entrarás para ganar gratis ¿Cuánto mercancía.