Modelo adversario

En informática , un algoritmo en línea mide su competitividad frente a diferentes modelos adversarios . En el caso de los algoritmos deterministas, el adversario es el mismo que el adversario adaptativo fuera de línea. En el caso de los algoritmos en línea aleatorios, la competitividad puede depender del modelo adversario utilizado.

Los tres adversarios comunes son el adversario inconsciente, el adversario adaptativo en línea y el adversario adaptativo fuera de línea.

Al adversario inconsciente se lo suele llamar adversario débil. Este adversario conoce el código del algoritmo, pero no llega a conocer los resultados aleatorios del mismo.

El adversario en línea adaptable a veces se denomina adversario mediano. Este adversario debe tomar su propia decisión antes de que se le permita conocer la decisión del algoritmo.

Al adversario adaptativo offline a veces se lo llama adversario fuerte. Este adversario lo sabe todo, incluso el generador de números aleatorios. Este adversario es tan fuerte que la aleatorización no ayuda contra él.

De S. Ben-David, A. Borodin , R. Karp , G. Tardos y A. Wigderson tenemos:

• Si existe un algoritmo aleatorio que es α-competitivo contra cualquier adversario adaptativo fuera de línea, entonces también existe un algoritmo determinista α-competitivo.
• Si G es un algoritmo aleatorio c-competitivo contra cualquier adversario en línea adaptativo, y hay un algoritmo aleatorio d-competitivo contra cualquier adversario desprevenido, entonces G es un algoritmo aleatorio (c * d)-competitivo contra cualquier adversario adaptativo fuera de línea.

• Análisis competitivo (algoritmo online)
• Problema con el servidor K
• Algoritmo en línea

• Borodin, A. ; El-Yaniv, R. (1998). Computación en línea y análisis competitivo. Cambridge University Press. ISBN 978-0-521-56392-5.
• S. Ben-David; A. Borodin; R. Karp ; G. Tardos; A. Wigderson. (1994). "Sobre el poder de la aleatorización en algoritmos en línea" (PDF) . Algorithmica . 11 : 2–14. doi :10.1007/BF01294260.

• Bibliografía de artículos sobre algoritmos en línea