Algorithms for computing the optimal transitive approximation of a proximity relation

Three ways for generating the optimal transitive approximations or a suboptimal transitive approximation are given in this paper. The first one can obtain all the optimal transitive approximations for any proximity relation. However, trying to find all the optimal transitive approximations can be very expensive. The second one gives a method to obtain a suboptimal transitive approximation which can frequently generate an optimal transitive approximation. Furthermore, starting from the transitive closure the third method is proposed which can obtain a locally optimal transitive approximation. Finally, numerical experiments are carried out to show the abilities of these algorithms and compare them to other existing approximation algorithms.