BIRS Workshop Lecture Videos
Lower Bounds for Searching Robots, some Faulty Kupavskii, Andrey
Suppose we are sending out k robots from 0 to search the real line at a constant speed (with turns) to find a target at an unknown location; f of the robots are faulty, meaning that they fail to report the target although visiting its location. The goal is to find the target in time at most lambda |d|, if the target is located at d, |d|>1, for lambda as small as possible. In this work, we find a tight lower bound for lambda. This is joint work with Emo Welzl.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International