Search Balanced Trees (0,1)-Matrices Greedy Algorithm
Issue Date:
2003
Publisher:
Institute of Information Theories and Applications FOI ITHEA
Abstract:
Links and similarities between the combinatorial optimization problems and the hierarchical search
algorithms are discussed. One is the combinatorial greedy algorithm of step-by-step construction of the
column-constraint (0,1) matrices with the different rows. The second is the base search construction of
databases, - the class of the well known weight-balanced binary trees. Noted, that in some approximation
each of the above problems might be interpreted in terms of the second problem. The constraints in matrices
imply the novel concept of a differential balance in hierarchical trees. The obtained results extend the
knowledge for balanced trees and prove that the known greedy algorithm for matrices is applicable in the
world of balanced trees providing optimization on trees in layers.
Description:
* The research was supported by INTAS 00-397 and 00-626 Projects.