Final Exam Problem 1. Prove that no randomized online algorithm for the k-server problem can have competitiveness lower than k against the adaptive online adversary, as mentioned in http://www.egr.unlv.edu/~larmore/Courses/CSC789/Serv/pg06. You will use this result to work Problem 2 of the final exam. ----------------------------------------------------- Final Exam Problem 2. 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 M of at least 3 points. We have proved the following results in class. 1. HARMONIC is 2-competitive against the adaptive online adversary in M. 2. HARMONIC is 2-competitive against the oblivious adversary in M. 3. Random_Slack is 2-competitive against the adaptive online adversary in M. 4. Random_Slack is 2-competitive against the oblivious adversary in M. 5. There is no randomized online algorithm with competitiveness better than 2 against the adaptive online adversary for the 2-server problem in M. 6. There is no randomized online algorithm with competitiveness better than 3/2 against the oblivious adversary for the 2-server problem in M. Now, let M = {a,b,c} where ||a,b|| = 1, and ||a,c||= ||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. 1. The competitiveness of HARMONIC against the adaptive online adversary. 2. The competitiveness of HARMONIC against the oblivious adversary. 3. The competitiveness of Random_Slack against the adaptive online adversary. 4. The competitiveness of Random_Slack against the oblivious adversary. 5. The competitiveness of the best randomized online algorithm against the adaptive online adversary. 6. The competitiveness of the best randomized online algorithm against the oblivious adversary. ----------------------------------------------------- Mid-term Problem 1. Suppose that a metrical task system consists of a metric space M and all possible task vectors. Prove that, for any fixed epsilon > 0, we can assume, without loss of generality, that all tasks are of the form (0, ... 0,delta,0, ... 0) where delta <= epsilon. ----------------------------------------------------- Mid-term Problem 2. Consider the metrical task system consisting of two states, 1 and 2, where the distance between the states is 1; and two tasks, (0,2) and (1,0). The deterministic competitiveness of this MTS is 3/2. Find the randomized competitiveness against the oblivious adversary, and prove your answer, both as an upper and a lower bound.