Solution to Test Problem 1. I would like to first point out that I have not found a published proof of this important lemma that contains all the necessary details. The proofs out there consist largely of hand-waving, as far as I have been able to determine. Fix epsilon > 0. Let calR_1 be an adversary that makes only small elementary requests, i.e., requests of the form for delta <= epsilon. Let calA_1 be an online algorithm that is C-competitive against calR_1. We now define an online algorithm calA_2 that is C-competitive against any adversary. If calA_1 is deterministic, calA_2 will be deterministic, while if If calA_1 is randomized, calA_2 will be randomized. calA_2 operates by using calA_1 as a black box, and by using the requests it receives to give requests to that black box. It then uses the responses of calA_1 to formulate its own responses. Suppose that calA_2 is in state a. The invariant is that calA_1 is also in state a. Let r be a request. Then we give calA_1 an entire sequence of requests, which we call rho. If calA_1 moves to state c, then calA_2 moves to state b, serves r, then moves to state c, where b is defined so as to minimize the quantity d_{ab} + r(b) + d_{bc}. It remains to first describe rho, and then to prove that calA_2 is C-competitive. We will choose an integer m, to be decided later. Let s be the request sequence s = <1,r(1)/m> <2,r(2)/m> ... ... , and let rho = s^m. Lemma A: For any given states a and c, let cost(rho) be the optimal cost of servicing rho starting in state a and ending in state c, and let cost(r) be the optimal cost of servicing r starting in state a and ending in state c. Then (1) cost(rho) <= cost(r) (2) cost(r) <= cost(rho) + 2R(R+D)/m Proof of (1): The optimal service of r is min_b(d_{ab} + r(b) + d_{bc}). Starting in a, rho can be serviced at that cost by first moving to b, then serving all requests, then moving to c. Proof of (2): Let k be the number of states. Assume that 1 <= d_{ij} <= D for all distinct states i,j. Assume that r(i) <= R for all i. for any service sequence sigma for rho, we define an "internal switch" of sigma to be a change of state that is neither before rho nor after rho. Lemma B: There is a service of rho starting in state a and ending in state c whose cost is no greater than cost(rho) + R(R+D)/m. Proof of Lemma B: The optimal service can have cost at most R+D, and hence contains at most R+D internal switches. Each internal switch can be removed by increasing the cost at most R/m, as follows. Suppose that an internal switch is from state e to state f. Without loss of generality, r(e) <= r(f). Then modify the service by postponing that switch until either the next switch or the end of the sequence, whichever comes first. By the triangle inequality, there will be no increase in the movement cost. Consider the subsequence of rho where e is the state instead of f. In this subsequence, the number of requests of the form is at most one more than the number of requests of the form , thus the service cost cannot increase by more than r(e)/m <= R/m. If sigma is a service of rho starting in state a and ending in state c, and having no internal switches, then it must remain in some state b as it services all the requests. It follows that it must pay at least cost(r). This concludes the proof of Lemma A. We now prove that calA_2 is C-competitive. Let r^1 ... r^N be any request sequence. For the request r^t, we choose rho^t as in the above construction by picking an m large enough so that R(R+D)/m <= 2^{-t} and R/m < epsilon. From Lemma A, when then have (1) cost_opt(rho^1 ... rho^N) <= cost_opt(r^1 ... r^N) (2) cost_calA_2(r^1 ... r^N) <= cost_calA_1(rho^1 ... rho^N) + 1 Since, by hypothesis: cost_calA_1(rho^1 ... rho^N) <= C*cost_opt(rho^1 ... rho^N) + O(1) it follows that cost_calA_2(r^1 ... r^N) <= C*cost_opt(r^1 ... r^N) + O(1)