Abstract:

A new algorithm RMOP was obtained which is called random minimum order partition by improving FRT algorithm. In view of choosing a random permutation π for all points of the given metric space G, randomly selecting point u∈V, then the order Jr(u)=inf｛j∈N:d(πj,u)≤r,πj,u∈V｝ was derived. Therefore, a hierarchically well separated tree (short for HST) was constructed by recursively partitioning G via some clusters B(πJr(u),r), which πJr(u) is the center and r is the radius of the cluster. Moreover, the expectation expression E(dT(u,v))≤O(logn)d(u,v) holds. When FRT algorithm and RMOP algorithm have the same random permutation π, the probability which ensures the point u lies in the region B(πJr(u),r) is maximum in the RMOP algorithm.

Key words: HSTs; tree metrics; random partition; probabilistic approximation algorithm