Optimal Constructions of Hybrid Algorithms

Simple item page
dc.creatorKao, Ming-Yang
dc.creatorMa, Yuan
dc.creatorSipser, Michael
dc.creatorYin, Yiqun
dc.date2001-01-26
dc.date.accessioned2026-07-07T03:16:53Z
dc.date.available2026-07-07T03:16:53Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/cs/0101028
dc.identifierhttp://arxiv.org/abs/cs/0101028
dc.identifierJournal of Algorithms, 29:142--164, 1998
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30523
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.subjectF.2.2
dc.titleOptimal Constructions of Hybrid Algorithms
dc.typetext

Files

Collections

arXiv