Referent: Piotr Wójcik

Tytuł referatu: An Approximation Algorithm for Binary Searching in Trees

Streszczenie: We consider the problem of computing efficent strategies for searching in trees. As a generalization of the classical binary search for ordered lists, suppose one wishes to find a (unknown) specific node of tree by asking queries to its arcs, where each query indicates the endpoint closer to the desired node. Given the likelihood of each node being the one searched, the objective is to compute a search strategy that minimizes the expected number of queries. Practical applications of this problem include file system synchronization and software testing. Here we present a lineartime algorithm which is the first constant factor approximation for this problem. This represents a significant improvement over previous O(log n) approximation.