Appendix

Summary

Types of Adversaries and Their Relationships

Definition A.1.1 For randomized online algorithms, the oblivious adversary has to generate the entire input sequence in advance (using only the information about distribution used by the randomized algorithm) before any requests are served by the online algorithm. Thus, the adversary has no access to the random choices made by the algorithm. Moreover, OPT's cost is equal to the cost of the optimal offline algorithm knowing the entire input sequence in advance.

Let the oblivious adversary be denoted as Qo. Then Qo knows the distribution D used by the randomized algorithmR, but does not know the actual random choices made byR. Another way to describe this interaction is that Qo chooses input 1, 2, … , which is processed by R sequentially with decisions d1, d2, … and Qo has to make request i without any knowledge of d1, d2, … , di−1.

Definition A.1.2 For a minimization problem, a randomized algorithm R is -competitive against an oblivious adversary Qo if

whereis the input generated by Qo.

Definition A.1.3 Adaptive adversary Qa: Adversary is allowed to observe the online algorithm's decisions (random choices) and generate the next request based on that. Thus, Qa's request i can depend on d1, d2, … , di−1

Definition A.1.4 Adaptive offline adversary Qaf: Adversary is allowed to observe the online algorithm's decisions (random choices) and generate the next request based on that. Moreover, OPT is allowed access to this sequence offline and hence is charged the optimum offline cost for that sequence. Thus, once R has made its sequential decisions d1, d2, … , dn that can be used to generate 1, 2, … , n, OPT's cost is the cost incurred by the optimal offline algorithm knowing the full sequence 1, 2, … , n ahead of time.

A slightly weaker definition is as follows.

Definition A.1.5 Adaptive online adversary Qao: Adversary is allowed to observe the online algorithm's decisions (random choices) and generate the next request based on that. OPT, however, also must serve each request online, i.e., before knowing the random choices made by the online algorithm on the present request, which in turn possibly influences the next request made by the adversary.