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 -