Competitive Online Approximation of the Optimal Search Ratio
From MaRDI portal
Publication:3631895
DOI10.1137/060662204zbMath1187.68259OpenAlexW1965155276MaRDI QIDQ3631895
Tom Kamphans, Elmar Langetepe, Gerhard Trippen, Rolf Klein, Rudolf Fleischer
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
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
On the approximation of shortest escape paths, Lower and upper competitive bounds for online directed graph exploration, Online routing and searching on graphs with blocked edges, A general framework for searching on a line, Fibonacci helps to evacuate from a convex region in a grid network, Competitive search in a network, Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs, Impact of knowledge on the cost of treasure hunt in trees, The beachcombers' problem: walking and searching with mobile robots, Online search with a hint, Multi-target ray searching problems, The expanding search ratio of a graph, Online graph exploration algorithms for cycles and trees by multiple searchers, An improved online evacuation strategy from a convex region on grid networks, Beachcombing on strips and islands, Reaching a target in the plane with no information
