Optimal Constructions of Hybrid Algorithms
<|reference_start|>Optimal Constructions of Hybrid Algorithms: 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.<|reference_end|>
@article{kao2001optimal,
    title={Optimal Constructions of Hybrid Algorithms},
    author={Ming-Yang Kao, Yuan Ma, Michael Sipser, Yiqun Yin},
    journal={Journal of Algorithms, 29:142--164, 1998},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0101028},
    primaryClass={cs.DM cs.DS}
}