Competitive randomized algorithms for non-uniform problems

TLDR

Competitive analysis compares online algorithms to optimal offline ones, and randomization can improve worst‑case performance ratios, as illustrated by a 3/2 ratio on equilateral triangles. The paper introduces new randomized online algorithms for snoopy caching, the spin‑block problem, and the 2‑server problem on isosceles triangles, and also studies the case of unknown request distributions. These algorithms are randomized online strategies that achieve optimal competitive ratios, with deterministic adaptive variants for unknown distributions, and specialized constructions for the 2‑server problem on isosceles triangles. All presented algorithms attain the optimal competitive ratio \(e/(e-1)\approx1.58\) against an oblivious adversary, improving over the deterministic bound of 2, and deterministic adaptive algorithms also reach this ratio.

Abstract

Competitive analysis is concerned with comparing the performance of on-line algorithms with that of optimal off-line algorithms. In some cases randomization can lead to algorithms with improved performance ratios on worst-case sequences. In this paper we present new randomized on-line algorithms for snoopy caching and the spin-block problem. These algorithms achieve competitive ratios approachinge/(e−1) ≈ 1.58 against an oblivious adversary. These ratios are optimal and are a surprising improvement over the best possible ratio in the deterministic case, which is 2. We also consider the situation when the request sequences for these problems are generated according to an unknown probability distribution. In this case we show that deterministic algorithms that adapt to the observed request statistics also have competitive factors approachinge/(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 approache/(e−1). This compares with the ratio of 3/2 that can be achieved on an equilateral triangle.