En informática , un algoritmo en línea mide su competitividad frente a diferentes modelos de adversarios . Para los algoritmos deterministas, el adversario es el mismo que el adversario adaptativo fuera de línea. Para los algoritmos en línea aleatorios, la competitividad puede depender del modelo de adversario utilizado.
Adversarios comunes
Los tres adversarios comunes son el adversario inconsciente, el adversario adaptativo en línea y el adversario adaptativo fuera de línea.
El adversario inconsciente a veces se denomina adversario débil. Este adversario conoce el código del algoritmo, pero no llega a conocer los resultados aleatorios del algoritmo.
El adversario adaptativo en línea a veces se denomina adversario medio. Este adversario debe tomar su propia decisión antes de que se le permita conocer la decisión del algoritmo.
El adversario adaptativo fuera de línea a veces se denomina 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.
Resultados importantes
De S. Ben-David, A. Borodin , R. Karp , G. Tardos , A. Wigderson tenemos:
- Si hay 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 d-competitivo aleatorio contra cualquier adversario ajeno, entonces G es un algoritmo competitivo aleatorio (c * d) contra cualquier adversario fuera de línea adaptativo.
Ver también
Referencias
- Borodin, A .; El-Yaniv, R. (1998). Computación en línea y análisis competitivo . Prensa de la Universidad de Cambridge. 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) . Algoritmica . 11 : 2-14. doi : 10.1007 / BF01294260 .
Enlaces externos
