License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11812/
Go to the corresponding LIPIcs Volume Portal

Acharjee, Sumi ; Georgiou, Konstantinos ; Kundu, Somnath ; Srinivasan, Akshaya

Lower Bounds for Shoreline Searching With 2 or More Robots

pdf-format:
LIPIcs-OPODIS-2019-26.pdf (0.6 MB)

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
Collection: 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
Issue Date: 2020
Date of publication: 11.02.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI