Adversary model

In computer science, an online algorithm measures its competitiveness against different adversary models. For deterministic algorithms, the adversary is the same as the adaptive offline adversary. For randomized online algorithms competitiveness can depend upon the adversary model used.

Common adversaries

The three common adversaries are the oblivious adversary, the adaptive online adversary, and the adaptive offline adversary.

The oblivious adversary is sometimes referred to as the weak adversary. This adversary knows the algorithm's code, but does not get to know the randomized results of the algorithm.

The adaptive online adversary is sometimes called the medium adversary. This adversary must make its own decision before it is allowed to know the decision of the algorithm.

The adaptive offline adversary is sometimes called the strong adversary. This adversary knows everything, even the random number generator. This adversary is so strong that randomization does not help against it.

Important results

From S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson we have:

See also

References

External links


This article is issued from Wikipedia - version of the 7/2/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.