Algoritmos en línea

Los algoritmos en línea deben tomar decisiones irrevocables a medida que llega la entrada, sin conocimiento de solicitudes futuras; su calidad se mide mediante un análisis competitivo contra un algoritmo óptimo que ve toda la entrada por adelantado.

Definition

Un algoritmo en línea recibe su entrada como una secuencia de solicitudes y debe responder a cada una de forma inmediata e irrevocable sin ver solicitudes futuras; su relación competitiva es la relación en el peor de los casos de su costo con el costo de un algoritmo óptimo fuera de línea que conoce toda la secuencia de solicitudes.

Scope

Este tema cubre los algoritmos que procesan la entrada secuencialmente y se comprometen con las decisiones antes de que se conozca la entrada posterior, y el marco de relación competitiva utilizado para evaluarlos frente a un adversario fuera de línea óptimo. Incluye problemas clásicos —paginación y almacenamiento en caché, actualización de listas, el problema del alquiler de esquís, el problema del servidor k, y la programación en línea y el empaquetamiento de contenedores— y el papel de la aleatorización en la mejora de las relaciones competitivas frente a adversarios más débiles.

Core questions

• ¿Cómo se evalúan los algoritmos en línea cuando el futuro es desconocido?
• ¿Qué mide la relación competitiva y qué es el adversario fuera de línea?
• ¿Cómo ilustran los problemas clásicos como la paginación y el alquiler de esquís las compensaciones en línea?
• ¿Cómo puede la aleatorización mejorar la competitividad frente a un adversario ajeno?
• ¿Qué límites inferiores restringen la competitividad de cualquier algoritmo en línea?

Key concepts

• en línea versus fuera de línea
• relación competitiva
• adversario fuera de línea
• paginación y almacenamiento en caché
• actualización de listas
• problema del alquiler de esquís
• problema del servidor k
• competitividad aleatorizada

Key theories

Análisis competitivo

El análisis competitivo juzga un algoritmo en línea por la relación en el peor de los casos entre su costo y el de un algoritmo óptimo fuera de línea, ofreciendo una garantía que se mantiene para cualquier secuencia de entrada en lugar de depender de suposiciones sobre la entrada.

Aleatorización contra adversarios ajenos

Los algoritmos en línea aleatorizados pueden lograr relaciones competitivas estrictamente mejores que cualquier algoritmo determinista contra un adversario ajeno, porque el adversario debe fijar la entrada sin conocer las elecciones aleatorias del algoritmo.

Clinical relevance

Los algoritmos en línea modelan las decisiones que los sistemas toman en tiempo real sin conocimiento futuro: reemplazo de caché y páginas en sistemas operativos y CPU, autoorganización de estructuras de datos, asignación dinámica de recursos y equilibrio de carga, y decisiones de alquilar o comprar en la computación en la nube. El análisis competitivo ofrece garantías en el peor de los casos para tales sistemas reactivos.

History

El análisis competitivo fue introducido por Sleator y Tarjan en 1985 a través de su estudio de las reglas de actualización de listas y paginación, redefiniendo la evaluación de los algoritmos en línea en torno a la comparación con una solución óptima fuera de línea. El marco se expandió a través del problema del servidor k y los algoritmos en línea aleatorizados en la década de 1990, encuestados en la monografía de Borodin y El-Yaniv de 1998.

Key figures

• Daniel Sleator
• Robert Tarjan
• Allan Borodin
• Ran El-Yaniv

Seminal works

• sleator1985
• borodin1998
• cormen2009

Frequently asked questions

¿Qué es la relación competitiva?

Es la relación en el peor de los casos del costo de un algoritmo en línea con el costo de un algoritmo óptimo que ve toda la entrada por adelantado. Un algoritmo 2-competitivo nunca cuesta más del doble del mejor costo posible fuera de línea en cualquier secuencia de entrada.

¿Por qué la aleatorización ayuda a los algoritmos en línea?

Frente a un adversario ajeno que fija la entrada sin ver las elecciones aleatorias del algoritmo, la aleatorización evita que el adversario adapte un peor caso al comportamiento del algoritmo, permitiendo relaciones competitivas estrictamente mejores de lo que cualquier algoritmo determinista puede lograr.