Cicalese, Ferdinando and Keszegh, Balázs and Lidicky, Bernard and Pálvölgyi, Dömötör and Valla, Tomáš (2016) On the tree search problem with nonuniform costs. THEORETICAL COMPUTER SCIENCE, 647. pp. 2232. ISSN 03043975

Text
1404.4504v1.pdf Download (402kB)  Preview 
Abstract
Searching in partially ordered structures has been considered in the context of information retrieval and efficient treelike indices, as well as in hierarchy based knowledge representation. In this paper we focus on treelike 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 NonUniform 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. Finding the strategy guaranteeing the minimum possible cost is an NPcomplete problem already for input trees of degree 3 or diameter 6. The best known approximation guarantee was an O (logn/logloglogn)approximation algorithm of Cicalese et al. (2012) [4]. 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)aP proximation of the cost of the optimal strategy. In addition, we show that finding an optimal strategy is NPhard even when the input tree is a spider of diameter 6, i.e., at most,one vertex has degree larger than 2. (C) 2016 Elsevier B.V. All rights reserved.
Item Type:  Article 

Uncontrolled Keywords:  WEIGHTED TREES; Edge ranking; Approximation algorithm; Tree search problem; Trees (mathematics); Tree search; Partial order; Ordered structures; Optimal strategies; NPhard; Novel algorithm; Nonuniform; Associated costs; Parallel processing systems; Optimization; Optimal systems; KNOWLEDGE REPRESENTATION; Costs; Computational complexity; Approximation algorithms 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  19 Dec 2017 07:21 
Last Modified:  19 Dec 2017 07:21 
URI:  http://real.mtak.hu/id/eprint/71210 
Actions (login required)
Edit Item 