Unfair Problems and Randomized Algorithms for Metrical Task Systems

Borodin, Linial, and Saks introduced a general model for online systems calledmetrical task systems(1992, J. Assoc. Comput. Mach. 39(4), 745–763). In this paper, the unfair two state problem, a natural generalization of the two state metrical task system problem, is studied. A randomized algorithm for this problem is presented, and it is shown that this algorithm is optimal. Using the analysis of the unfair two state problem, a proof of a decomposition theorem similar to that of Blum, Karloff, Rabani, and Saks (1992, “Proc. 33rd Symposium on Foundations of Computer Science, ” pp. 197–207) is presented. This theorem allows one to design divide and conquer algorithms for specific metrical task systems. Our theorem gives the same bounds asymptotically, but it has less restrictive boundary conditions.

Authors

• Steve Seiden

Keywords

No keywords are indexed for this paper.