On the tree search problem with non-uniform costs

DOI10.1016/J.TCS.2016.07.019MaRDI QIDQ306704zbMATH OpenOpenAlexFDO

Authors Ferdinando Cicalese, Balázs Keszegh, Bernard Lidický, Dömötör Pálvölgyi, T. Valla

Publication date 1 September 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.4504

zbMATH Keywords

approximation algorithmtree search problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Approximation algorithms (68W25)

Abstract: Searching in partially ordered structures has been considered in the context of information retrieval and efficient tree-like indexes, 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: given a tree $T$ where each edge has 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 NP-complete problem already for input tree of degree 3 or diameter 6. The best known approximation guarantee is the $O(logn/logloglogn)$-approximation algorithm of [Cicalese et al. TCS 2012]. 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(fraclognloglogn)$-approximation of the cost of the optimal strategy. In addition, we show that finding an optimal strategy is NP-complete even when the input tree is a spider, i.e., at most one vertex has degree larger than 2.

Recommendations

• On the tree search problem with non-uniform costs
• On the complexity of searching in trees and partially ordered structures
• On the complexity of searching in trees: average-case minimization
• Improved approximation algorithms for the average-case tree searching problem
• Approximation strategies for generalized binary search in weighted trees

Cites work

• scientific article; zbMATH DE number 5764837 (Why is no real title available?)
• scientific article; zbMATH DE number 4057247 (Why is no real title available?)
• scientific article; zbMATH DE number 41347 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1303585 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• Edge ranking and searching in partial orders
• Edge ranking of weighted trees
• On an edge ranking problem of trees and graphs
• On minimum edge ranking spanning trees
• On the hardness of the minimum height decision tree problem
• Optimal Search in Trees
• Optimal edge ranking of trees in polynomial time
• Searching ordered structures
• The binary identification problem for weighted trees

Cited in

(11)

• Edge and pair queries-random graphs and complexity
• Cost-error relationships in A* tree-searching
• On the complexity of searching in trees and partially ordered structures
• A pathfinding problem for search trees with unknown edge length
• Competitive Online Search Trees on Trees
• On the complexity of searching in trees: average-case minimization
• On the tree search problem with non-uniform costs
• Partial order multiway search
• The complexity of bicriteria tree-depth
• The complexity of bicriteria tree-depth
• On binary searching with non-uniform costs

This page was built for publication: On the tree search problem with non-uniform costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306704)