TY - GEN

T1 - Optimal constructions of hybrid algorithms

AU - Kao, Ming Yang

AU - Ma, Yuan

AU - Sipser, Michael

AU - Yin, Yiqun

N1 - Funding Information:
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 λ F 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 solve Q in finite time, and all of 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 competiti¤e ratios to measure the efficiency of a hybrid algorithm, we construct an optimal deterministic hybrid algorithm and an efficient * A preliminary version of this work appeared in ``Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, 1994,'' pp., 372–381. The first author was supported in part by NSF grant CCR-9101385. The other three authors were supported in part by AFOSR contract F49620-92-J-0125, DARPA contract N00014-91-J-1698, and DARPA contract N00014-92-J-1799. This work was performed while the third and the fourth authors were with the Department of Mathematics and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139.

PY - 1994

Y1 - 1994

N2 - We study on-line strategies for solving problems with hybrid algorithms in the following situation: There is a problem Q and w basic algorithms for solving Q. We have a computer with λ≤w 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 will run forever without solving Q. A natural way to solve Q is to use a hybrid algorithm constructed from the basic algorithms. That is, 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 by optimizing the time spent running a given basic algorithm before switching to one of the alternatives. We use the notion of a competitive ratio to measure the efficiency of a hybrid algorithm. We construct optimal deterministic hybrid algorithms and efficient randomized hybrid algorithms. This resolves an open question posed by Baeza-Yates, Culberson, and Rawlins in the context of searching with multiple robots. We also prove that our randomized hybrid algorithms are optimal for λ = 1. This settles a conjecture of Kao, Reif, and Tate.

AB - We study on-line strategies for solving problems with hybrid algorithms in the following situation: There is a problem Q and w basic algorithms for solving Q. We have a computer with λ≤w 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 will run forever without solving Q. A natural way to solve Q is to use a hybrid algorithm constructed from the basic algorithms. That is, 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 by optimizing the time spent running a given basic algorithm before switching to one of the alternatives. We use the notion of a competitive ratio to measure the efficiency of a hybrid algorithm. We construct optimal deterministic hybrid algorithms and efficient randomized hybrid algorithms. This resolves an open question posed by Baeza-Yates, Culberson, and Rawlins in the context of searching with multiple robots. We also prove that our randomized hybrid algorithms are optimal for λ = 1. This settles a conjecture of Kao, Reif, and Tate.

UR - http://www.scopus.com/inward/record.url?scp=0028257192&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028257192&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0028257192

SN - 0898713293

T3 - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

SP - 372

EP - 381

BT - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

PB - Publ by ACM

T2 - Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms

Y2 - 23 January 1994 through 25 January 1994

ER -