1 Search Results for "Acharjee, Sumi"

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-dev.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}
}
  • Refine by Author
  • 1 Acharjee, Sumi
  • 1 Georgiou, Konstantinos
  • 1 Kundu, Somnath
  • 1 Srinivasan, Akshaya

  • Refine by Classification
  • 1 Computing methodologies → Continuous space search
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 2-Dimensional Search
  • 1 Competitive Analysis
  • 1 Lower Bounds
  • 1 Online Algorithms

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact