1 Search Results for "Wrosz, Izajasz"

Document
DOI: 10.4230/LIPIcs.MFCS.2022.42
Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times

Authors: Dariusz Dereniowski and Izajasz Wrosz

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

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.
Cite as

Dariusz Dereniowski and Izajasz Wrosz. Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.42},
  URN =		{urn:nbn:de:0030-drops-168405},
  doi =		{10.4230/LIPIcs.MFCS.2022.42},
  annote =	{Keywords: binary search, graph search, approximation algorithm, query complexity}
}
  • Refine by Author
  • 1 Dereniowski, Dariusz
  • 1 Wrosz, Izajasz

  • Refine by Classification
  • 1 Theory of computation
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 approximation algorithm
  • 1 binary search
  • 1 graph search
  • 1 query complexity

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

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