In our paper (2012) we introduced a special kind of k−1‐width junction tree, called k‐th order cherry tree in order to approximate a joint probability distribution. The approximation is the best if the Kullback‐Leibler divergence between the true joint probability distribution and the approximating one is minimal. Finding the best approximating k−1‐width junction tree probability distribution is NP‐complete if 2<k
<d−1, where d is the dimension of the joint probability distribution (see Karger and Srebro, 2001; Malvestuto, 2012). We also proved that the best approximating k−1‐width junction tree probability distribution can be embedded into a k‐th order cherry tree probability distribution. We introduce here a greedy algorithm resulting very good approximations in reasonable computing time. We prove then that if the Markov network which encodes the conditional independences of the multivariate probability distribution fulfills some requirements then our greedy algorithm is able to find the true probability distribution. Our algorithm uses just the k‐th order marginal probability distributions as input. We compare the results of the greedy algorithm proposed in this paper with the greedy algorithm proposed by Malvestuto (1991).
