On-line choice of on-line algorithms
Yossi Azar, Andrei Broder, Mark S. Manasse · 1993
Let fA1 ; A2 ; : : : ; Amg be a set of on-line algorithms for a problem P with input set I. We assume that P can be represented as a metrical task system. Each A i has a competitive ratio a i with respect to the optimum offline algorithm, but only for a subset of the possible inputs such that the union of these subsets covers I. Given this setup, we construct a generic deterministic on-line algorithm and a generic randomized on-line algorithm for P that are competitive over all possible inputs. We show that their competitive ratios are optimal up to constant factors. Our analysis proceeds via an amusing card game. 1 Introduction A common trick of the trade in algorithm design is to combine several algorithms using round robin execution. The basic idea is that, given a set of m algorithms for a problem P , one can simulate them one at a time in round robin fashion until the fastest of them solves P on the given input. It is easily seen that round robin execution is optimal among determ...