Unbounded lower bound for k-server against weak adversaries

We study the resource augmented version of the k-server problem, also known as the k-server problem against weak adversaries or the (h,k)-server problem. In this setting, an online algorithm using k servers is compared to an offline algorithm using h servers, where h ≤ k. For uniform metrics, it has been known since the seminal work of Sleator and Tarjan (1985) that for any ">0, the competitive ratio drops to a constant if k=(1+") · h. This result was later generalized to weighted stars (Young 1994) and trees of bounded depth (Bansal et al. 2017). The main open problem for this setting is whether a similar phenomenon occurs on general metrics. We resolve this question negatively. With a simple recursive construction, we show that the competitive ratio is at least ω(loglogh), even as k→∞. Our lower bound holds for both deterministic and randomized algorithms. It also disproves the existence of a competitive algorithm for the infinite server problem on general metrics.

• View at Publisher

Full Text ( Final Version , 717kb )

See Also
techReport Unbounded lower bound for k-server against weak adversaries M. Bienkowski (Marcin), J. Byrka (Jaroslaw), C.E. Coester (Christian) and Ł. Jeż (Łukasz)