2026-07-22T14:07:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7450 2024-03-06T10:40:27Z ddc:004 open_access

Approximation Strategies for Generalized Binary Search in Weighted Trees Dereniowski, Dariusz Kosowski, Adrian Uznanski, Przemyslaw Zou, Mengchuan Approximation Algorithm Adaptive Algorithm Graph Search Binary Search Vertex Ranking Trees We consider the following generalization of the binary search problem. A search strategy is required to locate an unknown target node t in a given tree T. Upon querying a node v of the tree, the strategy receives as a reply an indication of the connected component of T\{v} containing the target t. The cost of querying each node is given by a known non-negative weight function, and the considered objective is to minimize the total query cost for a worst-case choice of the target. Designing an optimal strategy for a weighted tree search instance is known to be strongly NP-hard, in contrast to the unweighted variant of the problem which can be solved optimally in linear time. Here, we show that weighted tree search admits a quasi-polynomial time approximation scheme (QPTAS): for any 0 < epsilon < 1, there exists a (1+epsilon)-approximation strategy with a computation time of n^O(log n / epsilon^2). Thus, the problem is not APX-hard, unless NP is contained in DTIME(n^O(log n)). By applying a generic reduction, we obtain as a corollary that the studied problem admits a polynomial-time O(sqrt(log n))-approximation. This improves previous tilde-O(log n)-approximation approaches, where the tilde-O-notation disregards O(poly log log n)-factors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dariusz Dereniowski and Adrian Kosowski and Przemyslaw Uznanski and Mengchuan Zou 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.84 urn:nbn:de:0030-drops-74507 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.84 eng https://creativecommons.org/licenses/by/3.0/legalcode