Approximation Strategies for Generalized Binary Search in Weighted 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 Tsetminusv 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: for any 0 textless varepsilon textless 1, there exists a (1+varepsilon)-approximation strategy with a computation time of nO(log n / varepsilon2). Thus, the problem is not APX-hard, unless NP subseteq DTIME(nO(log n)). By applying a generic reduction, we obtain as a corollary that the studied problem admits a polynomial-time O(√log n)-approximation. This improves previous hat O(log n)-approximation approaches, where the hat O-notation disregards O(polyloglog n)-factors.