Lower Bounds for Shoreline Searching with 2 or More Robots
share
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.
READ FULL TEXT