Optimal Constructions of Hybrid Algorithms

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)142-164
Number of pages23
JournalJournal of Algorithms
Volume29
Issue number1
DOIs
StatePublished - Oct 1998

Keywords

  • Competitive analysis
  • Cow-path problems
  • Hybrid algorithms
  • Online algorithms
  • Search with uncertainty

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Optimal Constructions of Hybrid Algorithms'. Together they form a unique fingerprint.

Cite this