nmber of connections per node which makes the majority of the Markov blankets small enough to be tractable for the bound propagation algorithm.

We want to discuss one important property of the bound propagation algorithm we did not address before. In this article we found our set of S,,,,'s by Equation 13. Due to this choice the separator nodes will always be in the neighbourhood of Smar. We have, however, much more freedom to choose S ten . In Section 2 we stated that a sufficient condition to make the algorithm tractable is that ‖ S,ep ∪ Smar ∪ Soth ‖ is small enough to do exact computations. A more general, but still sufficient condition is that we should choose S tep such that p ( Smar | S,ep ) can be computed efficiently, since this is the quantity we need (see Equation 9). If the network structure inside the area separated by S,,, can be written as a junction tree with a small enough tree width, we can compute these conditional probabilities en if the number of nodes enclosed by S,ep is very large. For certain architectures the separator can even in that case be small enough. One can think of a network consisting of a number of tractable junction trees that are connected to each other by a small number of nodes.  One should be aware of the important difference between the method outlined here and the method of conditioning (Pearl, 1988), which does exact inference. We do not require the part of the network that is outside the separator (i.e. all nodes not in S iss , Smar or Soth) to be tractable. The open problem is to develop an efficient algorithm to find suitable separators, since the nodes in such an S,ep are generally spread widely.

To conclude this article we like to say a few more words about linear programming.  This is a field of research that is still developing. Any improvements on LP-solving algorithms directly influence the results presented in this article.  We could imagine that more advanced LP-methods could benefit from the fact that the matrix A in Equation 10 is sparse.  At least half of the entries are zero. To be more precise: the constraints induced by a particular S f are exactly 2 ‖ S may ‖ rows in the matrix A with exactly 2 ‖ S,ep ‖ non-zero entries, thus having a fraction of 1 - 1/ || S™ || zeros.  Moreover, all the non-zero entries are ones. Finally, there is a promising future for LP-solvers, since the algorithms seems to be suitable for parallel computing (Alon & Megiddo, 1990).

## Acknowledgments

This research is supported by the Technology Foundation STW, applied science devision of NWO and the technology programme of the Ministry of Economic Affairs.

## References

Alon, N., & Megiddo, N. (1990). Parallel linear programming in fixed dimension almost surely in constant time. In IEEE Symposium on Foundations of Computer Science, p. 574-582.

Beinlich, I., Suermondt, G., Chavez, R., & Cooper, G. (1989). The ALARM monitoring stem: A case study with two probabilistic inference techniques for belief networks. In Proceedings of the 2nd European Conference on AI and Medicine . Springer-Verlag, Berlin.