Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
From MaRDI portal
Publication:675058
DOI10.1006/inco.1996.0092zbMath0876.68030OpenAlexW1975581626MaRDI QIDQ675058
Stephen R. Tate, Ming-Yang Kao, John H. Reif
Publication date: 6 March 1997
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: http://libres.uncg.edu/ir/uncg/f/S_Tate_Searching_1996.pdf
Searching and sorting (68P10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Linear Search with Terrain-Dependent Speeds ⋮ Bike assisted evacuation on a line ⋮ A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line ⋮ Further connections between contract-scheduling and ray-searching problems ⋮ Querying with Uncertainty ⋮ A Water-Filling Primal-Dual Algorithm for Approximating NonLinear Covering Problems ⋮ Evacuating from \(\ell_p\) unit disks in the wireless model (extended abstract) ⋮ Treasure Hunt with Advice ⋮ Multi-processor search and scheduling problems with setup cost ⋮ The ANTS problem ⋮ Incremental facility location problem and its competitive algorithms ⋮ Scheduling search procedures: The wheel of fortune ⋮ Online search for a hyperplane in high-dimensional Euclidean space ⋮ Pebble guided optimal treasure hunt in anonymous graphs ⋮ A \(o(n)\)-competitive deterministic algorithm for online matching on a line ⋮ Best-of-both-worlds analysis of online search ⋮ Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs ⋮ Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling ⋮ Evacuating from \(\ell_p\) unit disks in the wireless model ⋮ Impact of knowledge on the cost of treasure hunt in trees ⋮ The beachcombers' problem: walking and searching with mobile robots ⋮ Online minimization knapsack problem ⋮ Weighted online search ⋮ Overcoming probabilistic faults in disoriented linear search ⋮ A nearly tight lower bound for the \(d\)-dimensional cow-path problem ⋮ Optimal circle search despite the presence of faulty robots ⋮ Search Games: A Review ⋮ Extreme statistics of superdiffusive Lévy flights and every other Lévy subordinate Brownian motion ⋮ Algorithms for \(p\)-Faulty Search on a half-line ⋮ Online search with a hint ⋮ Finding defectives on a line by random docking and interval group tests ⋮ Deterministic treasure hunt in the plane with angular hints ⋮ Flood search under the California split rule. ⋮ Online algorithms for searching and exploration in the plane ⋮ Treasure evacuation with one robot on a disk ⋮ Multi-target ray searching problems ⋮ Event-driven optimal control for a robotic exploration, pick-up and delivery problem ⋮ Better Upper Bounds for Searching on a Line with Byzantine Robots ⋮ Lower bounds for searching robots, some faulty ⋮ The expanding search ratio of a graph ⋮ Infinite linear programming and online searching with turn cost ⋮ How unsplittable-flow-covering helps scheduling with job-dependent cost functions ⋮ Linear search by a pair of distinct-speed robots ⋮ Incremental medians via online bidding ⋮ The ultimate strategy to search on \(m\) rays? ⋮ On the two-dimensional cow search problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast two-robot disk evacuation with wireless communication ⋮ Online searching with turn cost ⋮ Online facility assignment ⋮ Wireless evacuation on \(m\) rays with \(k\) searchers ⋮ Searching for a non-adversarial, uncooperative agent on a cycle ⋮ Greedy metric minimum online matchings with random arrivals ⋮ Byzantine fault tolerant symmetric-persistent circle evacuation ⋮ Time-energy tradeoffs for evacuation by two robots in the wireless model ⋮ Linear rendezvous with asymmetric clocks ⋮ Ranking hypotheses to minimize the search cost in probabilistic inference models ⋮ Competitive Searching for a Line on a Line Arrangement. ⋮ Energy Consumption of Group Search on a Line ⋮ Rendezvous in planar environments with obstacles and unknown initial distance ⋮ New algorithms for related machines with temporary jobs. ⋮ Weighted group search on a line \& implications to the priority evacuation problem ⋮ Pebble guided near optimal treasure hunt in anonymous graphs
