Competitive Online Approximation of the Optimal Search Ratio
Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen · SIAM Journal on Computing · 2008
How efficiently can we search an unknown environment for a goal in an unknown position? How much would it help if the environment were known? We answer these questions for simple polygons and for undirected graphs by providing online search strategies that are as good as the best offline search algorithms, up to a constant factor. For other settings we prove that no such online algorithms exist. We introduce a natural measure which gives reasonable results and is more realistic than pure pessimistic competitive analysis.