BIRS Workshop Lecture Videos

Banff International Research Station Logo

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 Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International