Search
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 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.
Citations
-
0
CrossRef
-
0
Web of Science
-
1 0
Scopus
Authors (4)
-
Adrian Kosowski
- Université Paris Diderot
-
Przemysław Uznański
- ETH Zürich
-
Mengchuan Zou
- Université Paris Diderot
Cite as
Full text
full text is not available in portal
Keywords
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:
- 1868-8969
- 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.1-14
- DOI:
- Digital Object Identifier (open in new tab) 10.4230/lipics.icalp.2017.84
- Verified by:
- Gdańsk University of Technology
seen 151 times