Optimal Constructions of Hybrid Algorithms

Details Optimal Constructions of Hybrid Algorithms Optimal Constructions of Hybrid Algorithms

2001-01-26

arxiv.org/abs/cs/0101028v1

Journal of Algorithms, 29:142--164, 1998

Computer Science

Discrete Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Optimal Constructions of Hybrid Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Constructions of Hybrid Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Constructions of Hybrid Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-389731