The Taub Faculty of Computer Science Events and Talks

The hierarchical clustering problem deals with the construction of an M-layer hierarchical partition of a given graph. Every pair of vertices in the graph is associated with a layer. The objective is to construct a hierarchical partition that separates vertices as close as possible to their associated layer. It is proven that any approximation algorithm for this problem, induces an approximation algorithm of the same factor, for the problem of fitting tree metrics to general data, so as to minimize the additive error. The need to fit tree metrics to general data arises in several disciplines, such as in numerical taxonomy, in which fitting a tree metric to the data, could assist in learning the evolution tree. We consider two special cases of the hierarchical clustering problem. The first, is the sequential multicut problem, which is the hierarchical version of the well-known multicut problem. The second, mainly assumes the given graph is a tree. We present an O(log n)-approximation algorithm for the first case, and a bi-criteria, O(1)-approximation algorithm for the second.