TY - JOUR
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 - 1998/10
Y1 - 1998/10
N2 - 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 λ ≤ 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 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 λ = 1, settling a conjecture of Kao, Reif, and Tate.
AB - 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 λ ≤ 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 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 λ = 1, settling a conjecture of Kao, Reif, and Tate.
KW - Competitive analysis
KW - Cow-path problems
KW - Hybrid algorithms
KW - Online algorithms
KW - Search with uncertainty
UR - http://www.scopus.com/inward/record.url?scp=0004490780&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0004490780&partnerID=8YFLogxK
U2 - 10.1006/jagm.1998.0959
DO - 10.1006/jagm.1998.0959
M3 - Article
AN - SCOPUS:0004490780
VL - 29
SP - 142
EP - 164
JO - Journal of Algorithms
JF - Journal of Algorithms
SN - 0196-6774
IS - 1
ER -