License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.42
URN: urn:nbn:de:0030-drops-168405
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16840/
Go to the corresponding LIPIcs Volume Portal

Dereniowski, Dariusz ; Wrosz, Izajasz

Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times

pdf-format:
LIPIcs-MFCS-2022-42.pdf (0.7 MB)

Abstract

We consider a generalization of binary search in linear orders to the domain of weighted trees. The goal is to design an adaptive search strategy whose aim is to locate an unknown target vertex of a given tree. Each query to a vertex v incurs a non-negative cost ω(v) (that can be interpreted as the duration of the query) and returns a feedback that either v is the target or the edge incident to v is given that is on the path towards the target. The goal of the algorithm is to find a strategy that minimizes the worst-case total cost. We propose a constant-factor approximation algorithm for trees with a monotonic cost function. Such function is defined as follows: there exists a vertex r such that for any two vertices u,v on any path connecting r with a leaf it holds that if u is closer to r than v, then ω(u) ≥ ω(v). The best known approximation algorithm for general weight functions has the ratio of O{√{log n}} [Dereniowski et al. ICALP 2017] and it remains as a challenging open question whether constant-factor approximation is achievable in such case. This gives our first motivation towards considering monotonic cost functions and the second one lies in the potential applications.

BibTeX - Entry

@InProceedings{dereniowski_et_al:LIPIcs.MFCS.2022.42,
  author =	{Dereniowski, Dariusz and Wrosz, Izajasz},
  title =	{{Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{42:1--42:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16840},
  URN =		{urn:nbn:de:0030-drops-168405},
  doi =		{10.4230/LIPIcs.MFCS.2022.42},
  annote =	{Keywords: binary search, graph search, approximation algorithm, query complexity}
}

Keywords: binary search, graph search, approximation algorithm, query complexity
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

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