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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2000
منشور خارجيًانعم
الحدث32nd Annual ACM Symposium on Theory of Computing, STOC 2000 - Portland, OR, الولايات المتّحدة
المدة: ٢١ مايو ٢٠٠٠٢٣ مايو ٢٠٠٠

سلسلة المنشورات

الاسمProceedings of the Annual ACM Symposium on Theory of Computing
رقم المعيار الدولي للدوريات (المطبوع)0737-8017

!!Conference

!!Conference32nd Annual ACM Symposium on Theory of Computing, STOC 2000
الدولة/الإقليمالولايات المتّحدة
المدينةPortland, OR
المدة٢١/٠٥/٠٠٢٣/٠٥/٠٠

قم بذكر هذا