Randomized algorithms for metrical task systems

Borodin et al. (1992) introduce a general model for online systems in [3] called task systems and show a deterministic algorithm which achieves a competitive ratio of 2n − 1 for any metrical task system with n states. We present a randomized algorithm which achieves a competitive ratio of e/(e − 1)n − 1/(e − 1) ≈ 1. 5820n − 0. 5820 for this same problem. For the uniform metric space, Borodin et al. present an algorithm which achieves a competitive ratio of 2H n, and they show a lower bound of H n, for any randomized algorithm. We improve their upper bound for the uniform metric space by showing a randomized algorithm which is (H n + O(√log n))-competitive.

Authors

• Sandy Irani
• Steve Seiden

Keywords

No keywords are indexed for this paper.