Adversary (online algorithm)
- Adversary (online algorithm)
In computer science, an online algorithm measures its competitiveness against different adversary models. For deterministic algorithms, the adversary is the same, 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 him.
Important results
* From S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson we have::* If there is a randomized algorithm that is α-competitive against any adaptive offline adversary then there also exists an α-competitive deterministic algorithm.:* If G is a c-competitive randomized algorithm against any adaptive online adversary, and there is a randomized d-competitive algorithm against any oblivious adversary, then G is a randomized (c * d)-competitive algorithm against any adaptive offline adversary.
ee also
* Competitive analysis (online algorithm)
* K-server problem
* Online algorithm
References
*cite book
authorlink = Allan Borodin
author = Borodin, A.
coauthors = El-Yaniv, R.
url = http://www.cs.technion.ac.il/~rani/book.html
title = Online Computation and Competitive Analysis
publisher = Cambridge University Press
year = 1998
id = ISBN 978-0-521-56392-5
* cite journal
author= S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson.
title= [http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/BORODIN/paper.pdf On the Power of Randomization in On-line Algorithms]
journal= Algorithmica
year= 1994 | volume= 11 | pages= 2–14
External links
* [http://www.cs.ucr.edu/~marek/pubs/online.bib Bibliography of papers on online algorithms]
Wikimedia Foundation.
2010.
Look at other dictionaries:
Online algorithm — In computer science, an online algorithm is one that can process its input piece by piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an… … Wikipedia
Competitive analysis (online algorithm) — Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is … Wikipedia
Online algorithm — En informatique, un algorithme online (algorithme en ligne) est un algorithme qui reçoit son entrée (son input) prédécoupée en petits morceaux, et qui commence à calculer dès le premier petit morceau reçu, puis continue à traiter, en série, les… … Wikipédia en Français
Randomized algorithm — Part of a series on Probabilistic data structures Bloom filter · Skip list … Wikipedia
Attacker — For the term attacker in computer security, see adversary (cryptography) and adversary (online algorithm). In some sports, an attacker is a specific type of player, usually one whose role involves aggressive play.In football, attackers are also… … Wikipedia
K-server problem — The k server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis (the other being metrical task systems).… … Wikipedia
Ski rental problem — The ski rental problem is the name given to a class of problems in which there is a choice between continuing to pay a repeating cost or paying a one time cost which eliminates or reduces the repeating cost. The problem Many online problems have… … Wikipedia
List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… … Wikipedia
Список терминов, относящихся к алгоритмам и структурам данных — Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавливается на информационные списки и глоссарии … Википедия
Список терминов — Список терминов, относящихся к алгоритмам и структурам данных Это сл … Википедия
