Better algorithms for unfair metrical task systems and applications

Amos Fiat, Manor Mendel

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

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(log2 n(log log n)2) competitive, improving on the best previous result of O(log5 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(log2 k).

שפה מקוריתאנגלית
כותר פרסום המארחProceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000
עמודים725-734
מספר עמודים10
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2000
פורסם באופן חיצוניכן
אירוע32nd Annual ACM Symposium on Theory of Computing, STOC 2000 - Portland, OR, ארצות הברית
משך הזמן: 21 מאי 200023 מאי 2000

סדרות פרסומים

שםProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (מודפס)0737-8017

כנס

כנס32nd Annual ACM Symposium on Theory of Computing, STOC 2000
מדינה/אזורארצות הברית
עירPortland, OR
תקופה21/05/0023/05/00

פורמט ציטוט ביבליוגרפי