Better Algorithms For Unfair Metrical Task Systems And Applications Export

@misc{citeulike:6014630, abstract = {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. A randomized algorithm for metrical task systems on general metric spaces, O((log n log log n) 2 ) competitive, improving on the best previous result of O(log 5 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 2 k). 4. An O(log 2 n) competitive randomized algorithm for metrical task systems on n equally spaced points on the line. Key words. online algorithms, randomized algorithms AMS subject classications. 68W20, 68W25, 68W40 1. }, author = {Fiat, Amos and Mendel, Manor}, citeulike-article-id = {6014630}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.7258}, keywords = {mts, online\_algorithms}, posted-at = {2009-10-27 07:59:20}, priority = {2}, title = {Better Algorithms For Unfair Metrical Task Systems And Applications}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.7258}, year = {2000} }

TY - ELEC ID - citeulike:6014630 L3 - citeulike-article-id:6014630 N2 - 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. A randomized algorithm for metrical task systems on general metric spaces, O((log n log log n) 2 ) competitive, improving on the best previous result of O(log 5 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 2 k). 4. An O(log 2 n) competitive randomized algorithm for metrical task systems on n equally spaced points on the line. Key words. online algorithms, randomized algorithms AMS subject classications. 68W20, 68W25, 68W40 1. TI - Better Algorithms For Unfair Metrical Task Systems And Applications KW - mts KW - online_algorithms AU - Fiat, Amos AU - Mendel, Manor PY - 2000/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.7258 ER -