Competitive Online Approximation of the Optimal Search Ratio

DOI10.1137/060662204MaRDI QIDQ3631895zbMATH OpenOpenAlexFDO

Authors Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen

Publication date 22 June 2009

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/060662204

zbMATH Keywords

competitive ratioexplorationnatural measuresearchingonline motion planning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Algorithms – ESA 2004
• Models and algorithms for online exploration and search.
• On-line search in two-dimensional environment
• scientific article; zbMATH DE number 2102754
• On-line search in two-dimensional environment

Cited in

(33)

• The expected asymptotical ratio for preemptive stochastic online problem
• Online searching with turn cost
• Algorithms – ESA 2004
• A general framework for searching on a line
• On the approximation of shortest escape paths
• Position-independent near optimal searching and on-line recognition in star polygons
• Optimal online \(k\)-min search
• A new competitive algorithm for agent searching in unknown streets
• The expanding search ratio of a graph
• On-line search in two-dimensional environment
• On-line search in two-dimensional environment
• Online search with a hint
• Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs
• Flood search under the California split rule.
• An improved online evacuation strategy from a convex region on grid networks
• Tight analysis of a self-approaching strategy for the online kernel-search problem
• scientific article; zbMATH DE number 2102754 (Why is no real title available?)
• scientific article; zbMATH DE number 2085302 (Why is no real title available?)
• Online graph exploration algorithms for cycles and trees by multiple searchers
• Online search with a hint
• Almost-optimal deterministic treasure hunt in arbitrary graphs
• Models and algorithms for online exploration and search.
• The beachcombers' problem: walking and searching with mobile robots
• Competitive search in a network
• Online routing and searching on graphs with blocked edges
• Lower and upper competitive bounds for online directed graph exploration
• Impact of knowledge on the cost of treasure hunt in trees
• The tourist in the shopping arcade
• Reaching a target in the plane with no information
• Beachcombing on strips and islands
• Fibonacci helps to evacuate from a convex region in a grid network
• Online Searching
• Multi-target ray searching problems

This page was built for publication: Competitive Online Approximation of the Optimal Search Ratio

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