Algoritmos en línea

Los algoritmos en línea son aquellos en los cuales la información se va ingresando parte por parte, por lo que no se conoce toda la información y se debe de decir en el momento en el que llega la información lo que se va a hacer sin conocer las entradas futuras. Estos algoritmos a diferencia de los algoritmos fuera de línea, que si conocen toda la información del sistema desde un inicio, no garantizan que se encuentre una solución óptima. El estudio de estos algoritmos se centra en la calidad de la decisión tomada al momento de que llega información nueva.

Aplicación en sistemas de alarmas contra desastres naturales

La aplicación de algoritmos en línea para redes de señales de alarmas de desastres naturales podría ser la de buscar los caminos más rápidos a los nodos que todavía no se les ha informado la noticia considerando que algunos de los nodos pueden sufrir desperfectos o estar deshabilitados. Cuando se vaya visitando los nodos para informar la advertencia se podría analizar los nodos vecinos y tomar una decisión sobre cuál es la mejor opción y diseminar el mensaje más rápido.

Los algoritmos en línea considerados para resolver problemas de redes usan la idea de asociar con cada vínculo un costo que es exponencial a la fracción de la capacidad del vínculo asignado a los circuitos salientes. El costo asociado con un vínculo en la red puede ser visto como el valor a la variable dual asociada con el vínculo mismo. El algoritmo entonces enruta cada solicitud a un costo mínimo.