DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2019.26

Lower Bounds for Shoreline Searching With 2 or More Robots

Authors: Sumi Acharjee, Konstantinos Georgiou, Somnath Kundu, and Akshaya Srinivasan

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

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.

Cite as

Sumi Acharjee, Konstantinos Georgiou, Somnath Kundu, and Akshaya Srinivasan. Lower Bounds for Shoreline Searching With 2 or More Robots. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 26:1-26:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@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}
}

Search Results

Documents authored by Kundu, Somnath

Lower Bounds for Shoreline Searching With 2 or More Robots

Abstract

Cite as

Thanks for your feedback!

Could not send message