Optimal constructions of hybrid algorithms

Ming Yang Kao*, Yuan Ma, Michael Sipser, Yiqun Yin

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
PublisherPubl by ACM
Pages372-381
Number of pages10
ISBN (Print)0898713293
StatePublished - 1994
EventProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms - Arlington, VA, USA
Duration: Jan 23 1994Jan 25 1994

Publication series

NameProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

Other

OtherProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms
CityArlington, VA, USA
Period1/23/941/25/94

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Optimal constructions of hybrid algorithms'. Together they form a unique fingerprint.

Cite this