We study on-line strategies for solving problems with hybrid algorithm
s. There is a problem Q and w basic algorithms for solving Q. For some
lambda less than or equal to w, we have a computer with lambda disjoi
nt memory areas, each of which can be used to run a basic algorithm an
d store its intermediate results. In the worst case, only one basic al
gorithm can solve Q in finite time, and all of the other basic algorit
hms run forever without solving Q. To solve Q with a hybrid algorithm
constructed from the basic algorithms, we run a basic algorithm for so
me 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 comp
etitive ratios to measure the efficiency of a hybrid algorithm, we con
struct an optimal deterministic hybrid algorithm and an efficient rand
omized hybrid algorithm. This resolves an open question on searching w
ith multiple robots posed by Baeza-Yates, Culberson, and Rawlins. We a
lso prove that our randomized algorithm is optimal for lambda = 1, set
tling a conjecture of Kao, Reif; and Tate. (C) 1998 Academic Press.