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 <i,delta> 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> ... <i,r(i)/m> ... <k,r(k)/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 <e,r(e)/m> is at most one
more than the number of requests of the form <f,r(f)/m>, 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)
