COMPETITIVE RANDOMIZED ALGORITHMS FOR NONUNIFORM PROBLEMS

Competitive analysis is concerned with comparing the performance of on -line algorithms with that of optimal off-line algorithms. In some cas es randomization can lead to algorithms with improved performance rati os on worst-case sequences. In this paper we present new ramdomized on -line algorithms for snoopy caching and the spin-block problem. These algorithms achieve competitive ratios approaching e/(e - 1) almost-equ al-to 1.58 against an oblivious adversary. These ratios are optimal an d are a surprising improvement over the best possible ratio in the det erministic case, which is 2. We also consider the situation when the r equest sequences for these problems are generated according to an unkn own probability distribution. In this case we show that deterministic algorithms that adapt to the observed request statistics also have com petitive factors approaching e/(e - 1). Finally, we obtain randomized algorithms for the 2-server problem on a class of isosceles triangles. These algorithms are optimal against an oblivious adversary and have competitive ratios that approach e/(e - 1). This compares with the rat io of 3/2 that can be achieved on an equilateral triangle.