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.
@InProceedings{acharjee_et_al:LIPIcs.OPODIS.2019.26, author = {Acharjee, Sumi and Georgiou, Konstantinos and Kundu, Somnath and Srinivasan, Akshaya}, title = {{Lower Bounds for Shoreline Searching With 2 or More Robots}}, booktitle = {23rd International Conference on Principles of Distributed Systems (OPODIS 2019)}, pages = {26:1--26:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-133-7}, ISSN = {1868-8969}, year = {2020}, volume = {153}, editor = {Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.26}, URN = {urn:nbn:de:0030-drops-118121}, doi = {10.4230/LIPIcs.OPODIS.2019.26}, annote = {Keywords: 2-Dimensional Search, Online Algorithms, Competitive Analysis, Lower Bounds} }
Feedback for Dagstuhl Publishing