Optimal Constructions of Hybrid Algorithms

Abstract

We study on-line strategies for solving problems with hybrid algorithms. There is a problemQandw basicalgorithms for solvingQ. For some λ ≤ w, we have a computer with λ 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 solveQin finite time, and all of the other basic algorithms run forever without solvingQ. To solveQwith ahybridalgorithm constructed from the basic algorithms, we run a basic algorithm for some time, then switch to another, and continue this process untilQis solved. The goal is to solveQin the least amount of time. Usingcompetitive ratiosto 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 λ = 1, settling a conjecture of Kao, Reif, and Tate.