A lower bound on the competitivity of memory less algorithms for a generalization of the CNN problem

摘要

We consider the CNN problem in arbitrary dimension, and over any metric space containing the integers. We prove that, in every dimension at least 2, no memoryless online algorithm can achieve a constant competitive ratio, under a weak symmetry constraint on the algorithm. This generalizes in several aspects the lower bounds obtained by Koutsoupias and Taylor [The CNN Problem and other k-server variants, Theoret. Comput. Sci. 324 (2004) 347-359] for the original problem. The proof consists in the analysis of carefully selected random walks, which appear naturally in the framework of memoryless algorithms.