2020/01/13 by Sumi Acharjee, Acharjee, Sumi, Konstantinos Georgiou +5 · 2 citations
Computer Science · Engineering · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #Transportation and Mobility Innovations #Underwater Vehicles and Communication Systems
paper · pdf · doi:10.48550/arxiv.2001.04311
openalex publication_date 2020/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Searching for a line on the plane with n unit speed robots is a classic online problem that dates back to the 50's, and for which competitive ratio upper bounds are known for every n≥ 1. In this work we improve the best lower bound known for n=2 robots from 1.5993 to 3. Moreover we prove that the competitive ratio is at least √(3) for n=3 robots, and at least 1/cos(π/n) for n≥ 4 robots. Our lower bounds match the best upper bounds known for n≥ 4, hence resolving these cases. To the best of our knowledge, these are the first lower bounds proven for the cases n≥ 3 of this several decades old problem.