We know that HARMONIC is 3-competitive and Random_Slack is 2-competitive
for the 2-server problem, but these results apply to arbitrary metric
spaces. Better results can sometimes be obtained by considering a specific
metric space.
Consider the 2-server problem in a uniform metric space U of at least 3 points.
We have proved the following results in class.
-
HARMONIC is 2-competitive against the adaptive online adversary in U.
-
HARMONIC is 2-competitive against the oblivious adversary in U.
-
Random_Slack is 2-competitive against the adaptive online adversary in U.
-
Random_Slack is 2-competitive against the oblivious adversary in U.
-
There is no randomized online algorithm with competitiveness better than 2
against the adaptive online adversary for the 2-server problem in U.
-
There is no randomized online algorithm with competitiveness better than 3/2
against the oblivious adversary for the 2-server problem in U.
Now, let M = {a,b,c} where d(a,b) = 1, and d(a,c) = d(b,c) = 2, namely
a triangle with sides 1,2,2. Give answers and proofs of your answers to
each of the following questions, each concerning the 2-server problem in M.
Both upper and lower bounds should be proved.
-
The competitiveness of HARMONIC against the adaptive online adversary.
-
The competitiveness of HARMONIC against the oblivious adversary.
-
The competitiveness of Random-Slack against the adaptive online adversary.
-
The competitiveness of Random-Slack against the oblivious adversary.
-
The competitiveness of the best randomized online algorithm against the
adaptive online adversary.
-
The competitiveness of the best randomized online algorithm against the
oblivious adversary.
This part is by far the hardest. Clues will be posted.