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.ITCS.2021.51
URN: urn:nbn:de:0030-drops-135902
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13590/
Go to the corresponding LIPIcs Volume Portal

Angelopoulos, Spyros

Online Search with a Hint

pdf-format:
LIPIcs-ITCS-2021-51.pdf (0.5 MB)

Abstract

The linear search problem, informally known as the cow path problem, is one of the fundamental problems in search theory. In this problem, an immobile target is hidden at some unknown position on an unbounded line, and a mobile searcher, initially positioned at some specific point of the line called the root, must traverse the line so as to locate the target. The objective is to minimize the worst-case ratio of the distance traversed by the searcher to the distance of the target from the root, which is known as the competitive ratio of the search.
In this work we study this problem in a setting in which the searcher has a hint concerning the target. We consider three settings in regards to the nature of the hint: i) the hint suggests the exact position of the target on the line; ii) the hint suggests the direction of the optimal search (i.e., to the left or the right of the root); and iii) the hint is a general k-bit string that encodes some information concerning the target. Our objective is to study the Pareto-efficiency of strategies in this model. Namely, we seek optimal, or near-optimal tradeoffs between the searcher’s performance if the hint is correct (i.e., provided by a trusted source) and if the hint is incorrect (i.e., provided by an adversary).

BibTeX - Entry

@InProceedings{angelopoulos:LIPIcs.ITCS.2021.51,
  author =	{Spyros Angelopoulos},
  title =	{{Online Search with a Hint}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{51:1--51:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{James R. Lee},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13590},
  URN =		{urn:nbn:de:0030-drops-135902},
  doi =		{10.4230/LIPIcs.ITCS.2021.51},
  annote =	{Keywords: Search problems, searching on the line, competitive analysis, predictions}
}

Keywords: Search problems, searching on the line, competitive analysis, predictions
Collection: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Issue Date: 2021
Date of publication: 04.02.2021

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