2020/11/28 by Spyros Angelopoulos, Angelopoulos, Spyros, Malachi Voss +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2011.14144
openalex publication_date 2020/11/28 · openalex created_date 2023/01/06 · openalex updated_date 2026/07/28
We study the setting in which a mobile agent must locate a hidden target in a bounded or unbounded environment, with no information about the hider's position. In particular, we consider online search, in which the performance of the search strategy is evaluated by its worst case competitive ratio. We introduce a multi-criteria search problem in which the searcher has a budget on its allotted search time, and the objective is to design strategies that are competitively efficient, respect the budget, and maximize the total searched ground. We give analytically optimal strategies for the line and the star environments, and efficient heuristics for general networks.