Abstract
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 nonnegative weight function, and the considered objective is to minimize the total query cost for a worstcase choice of the target. Designing an optimal strategy for a weighted tree search instance is known to be strongly NPhard, 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 quasipolynomial 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 APXhard, 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 polynomialtime O(sqrt(log n))approximation. This improves previous tildeO(log n)approximation approaches, where the tildeOnotation disregards O(poly log log n)factors.
Citations

0
CrossRef

0
Web of Science

0
Scopus
Authors (4)
Full text
full text is not available in portal
Details
 Category:
 Conference activity
 Type:
 publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
 Title of issue:
 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) strony 1  14
 ISSN:
 18688969
 Language:
 English
 Publication year:
 2017
 Bibliographic description:
 Dereniowski D., Kosowski A., Uznański P., Zou M.: Approximation Strategies for Generalized Binary Search in Weighted Trees// 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)/ ed. Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl Dagstuhl, Germany: , 2017, s.114
 DOI:
 Digital Object Identifier (open in new tab) 10.4230/lipics.icalp.2017.84
 Verified by:
 Gdańsk University of Technology
seen 23 times
Recommended for you
Exploiting multiinterface networks: Connectivity and Cheapest Paths
 A. Kosowski,
 A. Navarra,
 C. Pinotti