Randomized k-server algorithms for growth-rate bounded graphs

Yair Bartal, Manor Mendel

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


The k-server problem is a fundamental online problem where k mobile servers should be scheduled to answer a sequence of requests for points in a metric space as to minimize the total movement cost. While the deterministic competitive ratio is at least k, randomized k-server algorithms have the potential of reaching o(k)-competitive ratios. Prior to this work only few specific cases of this problem were solved. For arbitrary metric spaces, this goal may be approached by using probabilistic metric approximation techniques. This paper gives the first results in this direction, obtaining o(k)-competitive ratio for a natural class of metric spaces, including d-dimensional grids, and wide range of k.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)192-202
عدد الصفحات11
دوريةJournal of Algorithms
مستوى الصوت55
رقم الإصدار2
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - مايو 2005
منشور خارجيًانعم

ملاحظة ببليوغرافية

Funding Information:
✩ A preliminary version of this work appears in Proceedings of the 15th Annual ACM–SIAM Symposium on Discrete Algorithms, 2004, pp. 659–664. * Corresponding author. E-mail addresses: yair@cs.huji.ac.il (Y. Bartal), mendelma@yahoo.com (M. Mendel). 1 Supported in part by a grant from the Israeli Science Foundation (195/02). 2 Supported in part by the Landau Center.


أدرس بدقة موضوعات البحث “Randomized k-server algorithms for growth-rate bounded graphs'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا