On the tree search problem with non-uniform costs

dc.contributor.author Cicalese, Ferdinando
dc.contributor.author Keszegh, Balázs
dc.contributor.author Lidicky, Bernard
dc.contributor.author Pálvölgyid, Dömötör
dc.contributor.author Valla, Tomáš
dc.contributor.department Mathematics
dc.date 2019-02-02T06:36:01.000
dc.date.accessioned 2020-06-30T06:01:06Z
dc.date.available 2020-06-30T06:01:06Z
dc.date.copyright Fri Jan 01 00:00:00 UTC 2016
dc.date.issued 2016-09-27
dc.description.abstract <p><p id="x-x-x-x-x-sp0040">Searching in partially ordered structures has been considered in the context of information retrieval and efficient tree-like indices, as well as in hierarchy based knowledge representation. In this paper we focus on tree-like partial orders and consider the problem of identifying an initially unknown vertex in a tree by asking edge queries: an edge query e returns the component of T - e containing the vertex sought for, while incurring some known cost c(e). The Tree Search Problem with Non-Uniform Cost is the following: given a tree T on n vertices, each edge having an associated cost, construct a strategy that minimizes the total cost of the identification in the worst case. <br /><br />Finding the strategy guaranteeing the minimum possible cost is an NP-complete problem already for input trees of degree 3 or diameter 6. The best known approximation guarantee was an O (log n/log log log n)-approximation algorithm of Cicalese et al. (2012) [4]. <br /><br />We improve upon the above results both from the algorithmic and the computational complexity point of view: We provide a novel algorithm that provides an O (log n/log log n)-approximation of the cost of the optimal strategy. In addition, we show that finding an optimal strategy is NP-hard even when the input tree is a spider of diameter 6, i.e., at most one vertex has degree larger than 2.</p>
dc.description.comments <p>This is a manuscript of an article published as Cicalese, Ferdinando, Balázs Keszegh, Bernard Lidický, Dömötör Pálvölgyi, and Tomáš Valla. "On the tree search problem with non-uniform costs." <em>Theoretical Computer Science</em> 647 (2016): 22-32. doi:<a href="http://dx.doi.org/10.1016/j.tcs.2016.07.019" id="x-x-x-x-ddDoi" target="_blank">10.1016/j.tcs.2016.07.019</a>. Posted with permission.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/math_pubs/98/
dc.identifier.articleid 1053
dc.identifier.contextkey 9436527
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath math_pubs/98
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/54698
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/math_pubs/98/treesearch.pdf|||Sat Jan 15 02:37:53 UTC 2022
dc.source.uri 10.1016/j.tcs.2016.07.019
dc.subject.disciplines Computer Sciences
dc.subject.disciplines Discrete Mathematics and Combinatorics
dc.subject.keywords Tree search problem
dc.subject.keywords Approximation algorithm
dc.title On the tree search problem with non-uniform costs
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication a1d8f5ab-9124-4104-981c-8ba1e426e3ff
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
498.16 KB
Adobe Portable Document Format