2026-08-02T16:29:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11812 2024-03-06T10:48:50Z ddc:004 open_access

Lower Bounds for Shoreline Searching With 2 or More Robots Acharjee, Sumi Georgiou, Konstantinos Kundu, Somnath Srinivasan, Akshaya 2-Dimensional Search Online Algorithms Competitive Analysis Lower Bounds 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 √{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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sumi Acharjee and Konstantinos Georgiou and Somnath Kundu and Akshaya Srinivasan 2020 Is Part Of LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2019.26 urn:nbn:de:0030-drops-118121 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.26 eng https://creativecommons.org/licenses/by/3.0/legalcode