  We study on-line strategies for solving problems with hybrid algorithms.
There is a problem Q and w basic algorithms for solving Q. For some lambda <=
w, we have a computer with lambda disjoint memory areas, each of which can be
used to run a basic algorithm and store its intermediate results. In the worst
case, only one basic algorithm can solve Q in finite time, and all the other
basic algorithms run forever without solving Q. To solve Q with a hybrid
algorithm constructed from the basic algorithms, we run a basic algorithm for
some time, then switch to another, and continue this process until Q is solved.
The goal is to solve Q in the least amount of time. Using competitive ratios to
measure the efficiency of a hybrid algorithm, we construct an optimal
deterministic hybrid algorithm and an efficient randomized hybrid algorithm.
This resolves an open question on searching with multiple robots posed by
Baeza-Yates, Culberson and Rawlins. We also prove that our randomized algorithm
is optimal for lambda = 1, settling a conjecture of Kao, Reif and Tate.

Discrete Mathematics;Data Structures and Algorithms