Making Rigid Hierarchies Flatter

On the theory side, we have settled the complexity of the problem, which had been open for eight years despite a considerable amount of previous work. Furthermore, we have given the first constant factor approximations for two different optimization terms, and we have identified a restricted problem version that is relevant in practice and allows for computing optimal solutions in polynomial time. On the experimental side, we have conducted an extensive study of the numerous hotlink assignment methods that have been proposed in the past five years, and we propose a heuristic that outperforms all known approximation algorithms in terms of solution quality.