
























We show how to restrict the analysis of a class of online problems that includes the $k$-server problem in finite metrics such that we only have to consider finite sequences of request. When applying the restrictions, both the optimal offline solutions and the best possible deterministic or randomized online solutions only differ by at most an arbitrarily small constant factor from the corresponding solutions without restrictions. Furthermore, we show how to obtain an algorithm with best possible deterministic or randomized competitive ratio for the restricted setup. Thus, for each fixed finite metrics our result qualifies as a competitive ratio approximation scheme as defined by Günther et al.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。