Motståndarmodell
Inom datavetenskap mäter en onlinealgoritm sin konkurrenskraft mot olika motståndarmodeller . För deterministiska algoritmer är motståndaren densamma som den adaptiva offline-motståndaren. För randomiserade onlinealgoritmer kan konkurrenskraften bero på vilken motståndarmodell som används.
Vanliga motståndare
De tre vanliga motståndarna är den omedvetna motståndaren, den adaptiva online-motståndaren och den adaptiva offline-motståndaren.
Den omedvetna motståndaren kallas ibland för den svage motståndaren. Denna motståndare känner till algoritmens kod, men får inte veta de randomiserade resultaten av algoritmen.
Den adaptiva online-motståndaren kallas ibland för medium-motståndaren. Denna motståndare måste fatta sitt eget beslut innan den får veta algoritmens beslut.
Den adaptiva offline-motståndaren kallas ibland den starka motståndaren. Den här motståndaren vet allt, även slumptalsgeneratorn. Denna motståndare är så stark att randomisering inte hjälper mot den.
Viktiga resultat
Från S. Ben-David, A. Borodin , R. Karp , G. Tardos , A. Wigderson har vi:
- Om det finns en randomiserad algoritm som är α-kompetitiv mot någon adaptiv offline-motståndare så finns det också en α-kompetitiv deterministisk algoritm.
- Om G är en c-kompetitiv randomiserad algoritm mot valfri adaptiv online-motståndare, och det finns en randomiserad d-kompetitiv algoritm mot vilken som helst omedveten motståndare, då är G en randomiserad (c * d)-kompetitiv algoritm mot valfri adaptiv offline-motståndare.
Se även
- Borodin, A .; El-Yaniv, R. (1998). Onlineberäkning och konkurrensanalys . Cambridge University Press. ISBN 978-0-521-56392-5 .
- S. Ben-David; A. Borodin; R. Karp ; G. Tardos; A. Wigderson. (1994). "Om kraften i randomisering i onlinealgoritmer" (PDF) . Algoritmik . 11 : 2–14. doi : 10.1007/BF01294260 .