Better algorithms for unfair metrical task systems and applications

Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these techniques to obtain the following results: 1. Better randomized algorithms for unfair metrical task systems on the uniform metric space. 2. Better randomized algorithms for metrical task systems on general metric spaces, O(log² n(log log n)²) competitive, improving on the best previous result of O(log⁵ n log log n). 3. A tight randomized competitive ratio for the k-weighted caching problem on k+1 points, O(log k), improving on the best previous result of O(log² k).