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 -