Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
From MaRDI portal
Publication:675058
DOI10.1006/INCO.1996.0092zbMATH Open0876.68030OpenAlexW1975581626MaRDI QIDQ675058FDOQ675058
Authors: Ming-Yang Kao, J. Reif, Stephen R. Tate 
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
Recommendations
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Searching and sorting (68P10)
Cited In (71)
- Incremental medians via online bidding
- Rendezvous in planar environments with obstacles and unknown initial distance
- Online searching with turn cost
- Title not available (Why is that?)
- Weighted group search on a line \& implications to the priority evacuation problem
- Bike assisted evacuation on a line
- Event-driven optimal control for a robotic exploration, pick-up and delivery problem
- Finding defectives on a line by random docking and interval group tests
- Treasure evacuation with one robot on a disk
- Fast two-robot disk evacuation with wireless communication
- The expanding search ratio of a graph
- Pebble guided near optimal treasure hunt in anonymous graphs
- Best-of-both-worlds analysis of online search
- Search games: a review
- Deterministic treasure hunt in the plane with angular hints
- Better Upper Bounds for Searching on a Line with Byzantine Robots
- Linear search by a pair of distinct-speed robots
- Flood search under the California split rule.
- How unsplittable-flow-covering helps scheduling with job-dependent cost functions
- New algorithms for related machines with temporary jobs.
- Optimal circle search despite the presence of faulty robots
- Further connections between contract-scheduling and ray-searching problems
- Searching for a non-adversarial, uncooperative agent on a cycle
- Title not available (Why is that?)
- Scheduling search procedures: The wheel of fortune
- Incremental facility location problem and its competitive algorithms
- The ultimate strategy to search on \(m\) rays?
- Evacuating from \(\ell_p\) unit disks in the wireless model (extended abstract)
- A \(o(n)\)-competitive deterministic algorithm for online matching on a line
- Title not available (Why is that?)
- On the two-dimensional cow search problem
- Title not available (Why is that?)
- A near optimal algorithm for the extended cow-path problem in the presence of relative errors
- Weighted online search
- Online algorithms for searching and exploration in the plane
- Competitive search in symmetric trees
- Ranking hypotheses to minimize the search cost in probabilistic inference models
- A \(o(n)\)-competitive deterministic algorithm for online matching on a line
- The beachcombers' problem: walking and searching with mobile robots
- Online minimization knapsack problem
- Energy Consumption of Group Search on a Line
- Online search for a hyperplane in high-dimensional Euclidean space
- Linear Search with Terrain-Dependent Speeds
- Pebble guided optimal treasure hunt in anonymous graphs
- Online facility assignment
- Multi-processor search and scheduling problems with setup cost
- Evacuating from \(\ell_p\) unit disks in the wireless model
- Time-energy tradeoffs for evacuation by two robots in the wireless model
- Greedy metric minimum online matchings with random arrivals
- Querying with Uncertainty
- A Water-Filling Primal-Dual Algorithm for Approximating NonLinear Covering Problems
- The ANTS problem
- Wireless evacuation on \(m\) rays with \(k\) searchers
- Infinite linear programming and online searching with turn cost
- Multi-target ray searching problems
- Lower bounds for searching robots, some faulty
- Treasure hunt with advice
- Competitive Searching for a Line on a Line Arrangement.
- Linear rendezvous with asymmetric clocks
- Overcoming probabilistic faults in disoriented linear search
- Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs
- A nearly tight lower bound for the \(d\)-dimensional cow-path problem
- Extreme statistics of superdiffusive Lévy flights and every other Lévy subordinate Brownian motion
- Overcoming probabilistic faults in disoriented linear search
- Online search with a hint
- Byzantine fault tolerant symmetric-persistent circle evacuation
- Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling
- Impact of knowledge on the cost of treasure hunt in trees
- Algorithms for \(p\)-Faulty Search on a half-line
- Optimal circle search despite the presence of faulty robots
- Evacuation of equilateral triangles by mobile agents of limited communication range
This page was built for publication: Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q675058)
