Randomized algorithm for the k-server problem on decomposable spaces

Simple item page
dc.creatorNagy-György, Judit
dc.date2007-08-17
dc.date.accessioned2026-07-07T08:24:07Z
dc.date.available2026-07-07T08:24:07Z
dc.descriptionWe study the randomized k-server problem on metric spaces consisting of widely separated subspaces. We give a method which extends existing algorithms to larger spaces with the growth rate of the competitive quotients being at most O(log k). This method yields o(k)-competitive algorithms solving the randomized k-server problem, for some special underlying metric spaces, e.g. HSTs of "small" height (but unbounded degree). HSTs are important tools for probabilistic approximation of metric spaces.
dc.description11 pages
dc.identifierhttps://arxiv.org/abs/0708.2351
dc.identifierhttp://arxiv.org/abs/0708.2351
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/136232
dc.subjectData Structures and Algorithms
dc.subjectDiscrete Mathematics
dc.titleRandomized algorithm for the k-server problem on decomposable spaces
dc.typetext

Files

Collections

arXiv