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




Related Items

Linear Search with Terrain-Dependent SpeedsBike assisted evacuation on a lineA $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a LineFurther connections between contract-scheduling and ray-searching problemsQuerying with UncertaintyA Water-Filling Primal-Dual Algorithm for Approximating NonLinear Covering ProblemsEvacuating from \(\ell_p\) unit disks in the wireless model (extended abstract)Treasure Hunt with AdviceMulti-processor search and scheduling problems with setup costThe ANTS problemIncremental facility location problem and its competitive algorithmsScheduling search procedures: The wheel of fortuneOnline search for a hyperplane in high-dimensional Euclidean spacePebble guided optimal treasure hunt in anonymous graphsA \(o(n)\)-competitive deterministic algorithm for online matching on a lineBest-of-both-worlds analysis of online searchAlmost-Optimal Deterministic Treasure Hunt in Unweighted GraphsCompetitive kill-and-restart and preemptive strategies for non-clairvoyant schedulingEvacuating from \(\ell_p\) unit disks in the wireless modelImpact of knowledge on the cost of treasure hunt in treesThe beachcombers' problem: walking and searching with mobile robotsOnline minimization knapsack problemWeighted online searchOvercoming probabilistic faults in disoriented linear searchA nearly tight lower bound for the \(d\)-dimensional cow-path problemOptimal circle search despite the presence of faulty robotsSearch Games: A ReviewExtreme statistics of superdiffusive Lévy flights and every other Lévy subordinate Brownian motionAlgorithms for \(p\)-Faulty Search on a half-lineOnline search with a hintFinding defectives on a line by random docking and interval group testsDeterministic treasure hunt in the plane with angular hintsFlood search under the California split rule.Online algorithms for searching and exploration in the planeTreasure evacuation with one robot on a diskMulti-target ray searching problemsEvent-driven optimal control for a robotic exploration, pick-up and delivery problemBetter Upper Bounds for Searching on a Line with Byzantine RobotsLower bounds for searching robots, some faultyThe expanding search ratio of a graphInfinite linear programming and online searching with turn costHow unsplittable-flow-covering helps scheduling with job-dependent cost functionsLinear search by a pair of distinct-speed robotsIncremental medians via online biddingThe ultimate strategy to search on \(m\) rays?On the two-dimensional cow search problemUnnamed ItemUnnamed ItemFast two-robot disk evacuation with wireless communicationOnline searching with turn costOnline facility assignmentWireless evacuation on \(m\) rays with \(k\) searchersSearching for a non-adversarial, uncooperative agent on a cycleGreedy metric minimum online matchings with random arrivalsByzantine fault tolerant symmetric-persistent circle evacuationTime-energy tradeoffs for evacuation by two robots in the wireless modelLinear rendezvous with asymmetric clocksRanking hypotheses to minimize the search cost in probabilistic inference modelsCompetitive Searching for a Line on a Line Arrangement.Energy Consumption of Group Search on a LineRendezvous in planar environments with obstacles and unknown initial distanceNew algorithms for related machines with temporary jobs.Weighted group search on a line \& implications to the priority evacuation problemPebble guided near optimal treasure hunt in anonymous graphs