Optimal Constructions of Hybrid Algorithms

DOI10.1006/JAGM.1998.0959MaRDI QIDQ4217305zbMATH OpenOpenAlexFDO

Authors Yuan Ma, Michael Sipser, Yiqun Yin, Ming-Yang Kao

Publication date 23 August 1999

Published in Journal of Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/cs/0101028

zbMATH Keywords

hybrid algorithms

Mathematics Subject Classification ID

Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

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 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.

Recommendations

• scientific article; zbMATH DE number 1003269
• On-line parallel heuristics, processor scheduling and robot searching under the competitive framework
• Online Parallel Heuristics and Robot Searching under the Competitive Framework
• Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem

Cited in

(24)

• Ranking hypotheses to minimize the search cost in probabilistic inference models
• The expanding search ratio of a graph
• Lower bounds for searching robots, some faulty
• Further connections between contract-scheduling and ray-searching problems
• Competitive search in a network
• Treasure evacuation with one robot on a disk
• Multi-processor search and scheduling problems with setup cost
• Multi-target ray searching problems
• Search games: a review
• scientific article; zbMATH DE number 1003269 (Why is no real title available?)
• Hyperbolic Dovetailing
• Online algorithms for searching and exploration in the plane
• Querying with Uncertainty
• Infinite linear programming and online searching with turn cost
• Wireless evacuation on \(m\) rays with \(k\) searchers
• Lower bounds in on-line geometric searching
• The ultimate strategy to search on \(m\) rays?
• Parallel searching on m rays
• Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling
• Weighted online search
• A nearly tight lower bound for the d-dimensional cow-path problem
• Online search with a hint
• Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling
• Online search with a hint

This page was built for publication: Optimal Constructions of Hybrid Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4217305)