Dereniowski, Dariusz ;
Wrosz, Izajasz
ConstantFactor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times
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 nonnegative 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 worstcase total cost. We propose a constantfactor 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 constantfactor 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 = {{ConstantFactor 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:142:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772563},
ISSN = {18688969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16840},
URN = {urn:nbn:de:0030drops168405},
doi = {10.4230/LIPIcs.MFCS.2022.42},
annote = {Keywords: binary search, graph search, approximation algorithm, query complexity}
}
22.08.2022
Keywords: 

binary search, graph search, approximation algorithm, query complexity 
Seminar: 

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Issue date: 

2022 
Date of publication: 

22.08.2022 