Modelo adversario

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

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

Al adversario despistado se le suele llamar adversario débil. Este adversario conoce el código del algoritmo, pero desconoce los resultados aleatorios que genera.

Al adversario en línea adaptativo a veces se le llama adversario intermedio. Este adversario debe tomar su propia decisión antes de que se le permita conocer la decisión del algoritmo.

Al adversario adaptativo sin conexión se le suele llamar adversario fuerte. Este adversario lo sabe todo, incluso el generador de números aleatorios. Es tan fuerte que la aleatorización no sirve de nada contra él.

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

• Si existe un algoritmo aleatorio que sea α-competitivo frente a 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 adaptativo en línea, y hay un algoritmo aleatorio d-competitivo contra cualquier adversario ajeno, entonces G es un algoritmo aleatorio (c * d)-competitivo contra cualquier adversario adaptativo fuera de línea.

• Análisis de la competencia (algoritmo en línea)
• Problema del 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