Approximation Strategies for Generalized Binary Search in Weighted Trees

2 GANG - Networks, Graphs and Algorithms
IRIF - Institut de Recherche en Informatique Fondamentale, Inria de Paris
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\setminus\{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: for any $0 < \varepsilon < 1$, there exists a $(1+\varepsilon)$-approximation strategy with a computation time of $n^{O(\log n / \varepsilon^2)}$. Thus, the problem is not APX-hard, unless $NP \subseteq 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 $\hat O(\log n)$-approximation approaches, where the $\hat O$-notation disregards $O(\mathrm{poly}\log\log n)$-factors.
Keywords :
Type de document :
Communication dans un congrès
ICALP 2017 - 44th International Colloquium on Automata, Languages, and Programming, 2017, Warsaw, Poland. 80, pp.84:1--84:14, 2017, LIPIcs. 〈10.4230/LIPIcs.ICALP.2017.84〉

https://hal.inria.fr/hal-01470935
Soumis le : dimanche 26 février 2017 - 20:21:53
Dernière modification le : jeudi 18 octobre 2018 - 16:14:05
Document(s) archivé(s) le : samedi 27 mai 2017 - 12:23:42

Fichiers

main.pdf
Fichiers produits par l'(les) auteur(s)

Citation

Dariusz Dereniowski, Adrian Kosowski, Przemyslaw Uznanski, Mengchuan Zou. Approximation Strategies for Generalized Binary Search in Weighted Trees . ICALP 2017 - 44th International Colloquium on Automata, Languages, and Programming, 2017, Warsaw, Poland. 80, pp.84:1--84:14, 2017, LIPIcs. 〈10.4230/LIPIcs.ICALP.2017.84〉. 〈hal-01470935〉

Métriques

Consultations de la notice

345

Téléchargements de fichiers