Improved Approximation Algorithms for the Average-Case Tree Searching Problem
We study the following tree search problem: in a given tree T=(V,E) a vertex has been marked and we want to identify it. In order to locate the marked vertex, we can use edge queries. An edge query e asks in which ofthe two connected components of T?e the marked vertex lies. The worst-case scenario where one is interested in minimizing the maximum number of queries is well understood, and linear time algorithms are known for finding an optimal search strategy. Here we study the more involved average-case analysis: A function w:V??+ is given which measures the likelihood for a vertex to be the one marked, and we seek to determine the strategy (decision tree) that minimizes the weighted average number of queries.
approximation algorithms decision trees searching in trees average case analysis fptas