Approximation Strategies for Generalized Binary Search in Weighted Trees - Publication - Bridge of Knowledge

Search

Approximation Strategies for Generalized Binary Search in Weighted Trees

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)

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 109 times

Recommended for you

Meta Tags