Probabilistic approximation algorithm of metric spaces
Cai Yu-hu · Journal of Shandong University · 2013
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 J r(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(d T(u,v)) ≤ O(log n) 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.