Approximation Strategies for Generalized Binary Search in Weighted Trees - Publikacja - MOST Wiedzy

Wyszukiwarka

Approximation Strategies for Generalized Binary Search in Weighted Trees

Abstrakt

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.

Cytowania

  • 0
    CrossRef
  • 0
    Web of Science
  • 0
    Scopus

Dariusz Dereniowski, Adrian Kosowski, Przemysław Uznański, Mengchuan Zou. (2017). Approximation Strategies for Generalized Binary Search in Weighted Trees, 1-14. https://doi.org/10.4230/lipics.icalp.2017.84

Informacje szczegółowe

Kategoria:
Inna publikacyjna praca zbiorowa (w tym materiały konferencyjne)
Typ:
publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Tytuł wydania:
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) strony 1 - 14
ISSN:
1868-8969
Język:
angielski
Rok wydania:
2017
Opis bibliograficzny:
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: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017, s.1-14

wyświetlono 16 razy

Publikacje, które mogą cię zainteresować

Meta Tagi