Open Collections will undergo maintenance on Thursday, July 24th, 2025. The site will not be available from 8:00 AM - 9:00 AM PST and performance may be impacted from 9:00 AM - 12:00 PM PST.

BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Lower Bounds for Searching Robots, some Faulty Kupavskii, Andrey

Description

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

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International