Dereniowski, Dariusz ;
Kosowski, Adrian ;
Uznanski, Przemyslaw ;
Zou, Mengchuan
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 nonnegative weight function, and the considered objective is to minimize the total query cost for a worstcase choice of the target.
Designing an optimal strategy for a weighted tree search instance is known to be strongly NPhard, 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 quasipolynomial 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 APXhard, 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 polynomialtime O(sqrt(log n))approximation.
This improves previous tildeO(log n)approximation approaches, where the tildeOnotation disregards O(poly log log n)factors.
BibTeX  Entry
@InProceedings{dereniowski_et_al:LIPIcs:2017:7450,
author = {Dariusz Dereniowski and Adrian Kosowski and Przemyslaw Uznanski and Mengchuan Zou},
title = {{Approximation Strategies for Generalized Binary Search in Weighted Trees}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {84:184:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7450},
URN = {urn:nbn:de:0030drops74507},
doi = {10.4230/LIPIcs.ICALP.2017.84},
annote = {Keywords: Approximation Algorithm, Adaptive Algorithm, Graph Search, Binary Search, Vertex Ranking, Trees}
}
07.07.2017
Keywords: 

Approximation Algorithm, Adaptive Algorithm, Graph Search, Binary Search, Vertex Ranking, Trees 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 