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. 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. Prior to this work no result of this type was known beyond results for specific metric spaces.

שפה מקוריתאנגלית
מספר עמודים6
סטטוס פרסוםפורסם - 2004
פורסם באופן חיצוניכן
אירועProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., ארצות הברית
משך הזמן: 11 ינו׳ 200413 ינו׳ 2004


כנסProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
מדינה/אזורארצות הברית
עירNew Orleans, LA.

הערה ביבליוגרפית

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'. יחד הם יוצרים טביעת אצבע ייחודית.

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