Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2019.26
URN: urn:nbn:de:0030-drops-118121
URL: https://drops.dagstuhl.de/opus/volltexte/2020/11812/
Acharjee, Sumi ; Georgiou, Konstantinos ; Kundu, Somnath ; Srinivasan, Akshaya
Lower Bounds for Shoreline Searching With 2 or More Robots
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{acharjee_et_al:LIPIcs:2020:11812,
author = {Sumi Acharjee and Konstantinos Georgiou and Somnath Kundu and Akshaya Srinivasan},
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 = {Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11812},
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}
}
| Keywords: | 2-Dimensional Search, Online Algorithms, Competitive Analysis, Lower Bounds | |
| Seminar: | 23rd International Conference on Principles of Distributed Systems (OPODIS 2019) | |
| Issue date: | 2020 | |
| Date of publication: | 11.02.2020 |
