文章基本信息

标题：Lower Bounds for Shoreline Searching With 2 or More Robots
本地全文：下载
作者：Sumi Acharjee ; Konstantinos Georgiou ; Somnath Kundu 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：153
页码：1-11
DOI：10.4230/LIPIcs.OPODIS.2019.26
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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, see [Baeza-Yates and Schott, 1995]. In this work we improve the best lower bound known for n=2 robots [Baeza-Yates and Schott, 1995] from 1.5993 to 3. Moreover we prove that the competitive ratio is at least â^S{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.
关键词：2-Dimensional Search; Online Algorithms; Competitive Analysis; Lower Bounds