Wyszukiwarka
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
-
1 0
Scopus
Autorzy (4)
-
Adrian Kosowski
- Université Paris Diderot
-
Przemysław Uznański
- ETH Zürich
-
Mengchuan Zou
- Université Paris Diderot
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Aktywność konferencyjna
- 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: , 2017, s.1-14
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.4230/lipics.icalp.2017.84
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 153 razy