Show simple item record

dc.contributor.author
Dereniowski, Dariusz
dc.contributor.author
Kosowski, Adrian
dc.contributor.author
Uznanski, Przemyslaw
dc.contributor.author
Zou, Mengchuan
dc.contributor.editor
Chatzigiannakis, Ioannis
dc.contributor.editor
Indyk, Piotr
dc.contributor.editor
Kuhn, Fabian
dc.contributor.editor
Muscholl, Anca
dc.date.accessioned
2017-12-19T14:51:27Z
dc.date.available
2017-11-15T15:11:50Z
dc.date.available
2017-10-06T04:56:13Z
dc.date.available
2017-12-19T14:51:27Z
dc.date.issued
2017-07
dc.identifier.isbn
978-3-95977-041-5
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.ICALP.2017.84
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/222857
dc.identifier.doi
10.3929/ethz-b-000222857
dc.description.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.
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Computer Science
en_US
dc.subject
000 Computer science, knowledge, general works
en_US
dc.subject
Approximation Algorithm
en_US
dc.subject
Adaptive Algorithm
en_US
dc.subject
Graph Search
en_US
dc.subject
Binary Search
en_US
dc.subject
Vertex Ranking
en_US
dc.subject
Trees
en_US
dc.title
Approximation Strategies for Generalized Binary Search in Weighted Trees
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics
ethz.journal.volume
80
en_US
ethz.journal.abbreviated
Leibniz int. proc. inform.
ethz.pages.start
84:1
en_US
ethz.pages.end
84:14
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
en_US
ethz.event.location
Warsaw, Poland
en_US
ethz.event.date
July 10-14, 2017
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl, Germany
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
en_US
ethz.date.deposited
2017-10-06T04:56:18Z
ethz.source
FORM
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-12-19T14:51:29Z
ethz.rosetta.lastUpdated
2019-02-02T14:00:40Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/192350
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/208953
ethz.COinS
ctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.atitle=Approximation%20Strategies%20for%20Generalized%20Binary%20Search%20in%20Weighted%20Trees&amp;rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics&amp;rft.date=2017-07&amp;rft.volume=80&amp;rft.spage=84:1&amp;rft.epage=84:14&amp;rft.issn=1868-8969&amp;rft.au=Dereniowski,%20Dariusz&amp;Kosowski,%20Adrian&amp;Uznanski,%20Przemyslaw&amp;Zou,%20Mengchuan&amp;rft.isbn=978-3-95977-041-5&amp;rft.genre=proceeding&amp;rft_id=info:doi/978-3-95977-041-5&amp;rft.btitle=44th%20International%20Colloquium%20on%20Automata,%20Languages,%20and%20Programming%20(ICALP%202017)
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record