论文标题
使用2个或更多机器人搜索海岸线的下限
Lower Bounds for Shoreline Searching with 2 or More Robots
论文作者
论文摘要
在飞机上使用$ n $单位速度机器人在飞机上搜索一条线是一个经典的在线问题，其历史可以追溯到50年代，并且每$ n \ geq 1 $都知道竞争性比率上限。在这项工作中，我们将$ n = 2 $机器人闻名的最佳下限从1.5993提高到3。我们的下限与以$ n \ geq 4 $闻名的最佳上限匹配，因此可以解决这些案例。据我们所知，这些是这个数十年过去的问题的$ n \ geq 3 $所证明的第一个下限。
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\geq 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 $\sqrt{3}$ for $n=3$ robots, and at least $1/\cos(π/n)$ for $n\geq 4$ robots. Our lower bounds match the best upper bounds known for $n\geq 4$, hence resolving these cases. To the best of our knowledge, these are the first lower bounds proven for the cases $n\geq 3$ of this several decades old problem.
