Many combinatorial problems reduce to the optimal tree problem (OTP) – that of minimizing a cost function over a set of rooted trees with given leaves. No polynomial (by the number of leaves) approximation for OTP exists, but lower-bound estimates (LBE) are developed for many special cases. We propose a polynomial heuristic algorithm that employs these LBE. It combines greedy top-down tree construction with local search and parameters adjustment. The algorithm was successfully applied to the problems of decision tree growing and user interface structure optimization.
