Sie sind hier: Startseite Lehre Aktuelle Lehre Oberseminar CoNe (Computer Networks) The Hu-Tucker Algorithm via the Quadrangle Inequality

The Hu-Tucker Algorithm via the Quadrangle Inequality

Gastvortrag von Herrn Dr. Tobias Jacobs, National Institute of Informatics, Tokio

I present a novel analysis of the alphabetic tree problem. Instances of
this classic problem are characterized by n weighted terminals, and the
objective is to determine a binary search tree minimizing the weighted
total depth of the terminals subject to the constraint that the i-th
leaf from left-to-right corresponds to the i-th terminal. This is
equivalent to the problem of determining an optimal alphabetic binary
We reason about optimal alphabetic m-forests, i.e., forests consisting
of exactly m trees subject to the same constraints as in the alphabetic
tree problem. We analyze the process of successively computing the
optimal m-forest for m=n ...1 and prove a number of surprising
properties of that process.
The result of the analysis is a new elegant proof of the famous O(n log
n) time Hu-Tucker algorithm for the alphabetic tree problem. More
specifically, it can be show that this algorithm simulates the process
of computing optimal m-forests for decreasing values of m. The proof
reveals that the Quadrangle Inequality - which has been mainly known as
a speedup tool for dynamic programming methods - plays a central role
also for the correctness of the greedy Hu-Tucker algorithm.
Benutzerspezifische Werkzeuge