We will compute bounds for all S mar for which there can be found a separator in Ω. We reserve memory for p + ( Smar ) and p − ( Smar ) and initialize them to one and zero respectively. Note that if we have a bound over Smar it is still worthwhile to compute bounds over ssssees of Smar (e.g. Figure 1b and d). In contrast to a joint probability table, the bounds on marginals over subsets cannot be computed simply by summing over the marginal of Smar, since we have only bounds and not the real values.

## 3.1  The Iterative Part

For all S ten E Ω we perform the same action. First we set up the A and b for the LP-problem, since this depends only on S rep and the already computed bounds for which S rmar ⊆ S rep .

The number of variables in our LP-problem obviously is ‖ S,ep ‖. The number of (inequality)
constraints is equal to

$$\sum_{S_{\mathrm{mar}}\subseteq S_{\mathrm{sep}}}2\parallel S_{\mathrm{mar}}^{\prime}\parallel$$
$$\left(14\right)$$

Once the LP-problem is set up this far, we try to improve all bounds that are defined over an S mar for which S ten is its separator. The separator in figures 1b and d, for instance, is identical, but the Smar's differ. For each bound we iterate over its state space and set the c as in Equation 9 to its appropriate value. Then we compute the new upper and lower bounds for that s mar by solving the LP-problem twice: maximize and minimize. If the new found value improves the bound, we store it, otherwise we abandon it.

The iterative procedure is repeated until convergence is reached. In our simulations we define a bound as being converged as soon as the relative improvement after one iteration is less than one percent. If this holds for all bounds, the algorithms stops.

## 3.2 Computational Complexity

LP-problems have been thoroughly studied in the literature. The computational complexity of such problems is shown to be polynomial (Khachiyan, 1979). But more importantly, for most practical problems the number of iterations needed is close to linear in the number of variables or the number of constraints, whichever is less (Todd, 2002). In each iteration a
'pivoting action' needs to be performed, which is some operation that roughly accesses all the elements of the matrix A once. Therefore the expected computational complexity for solving one LP-problem is O ( m 2 ‖ S,ep ‖), where m is the number of constraints. The actual observed computation time depends heavily on the particular problem, but in general LP-
problems upto tens of thousands of variables and constraints are reasonable. This makes the presented method tractable for separators with ‖ S,ep ‖ of a similar size.

For every smar E Smar we need to solve two LP-problems: one for the upper and one for the lower bound. Note that in this iteration, we do not need to change the matrix A and vector 6 from Equation 10. The vector c , that defines the objective function, obviously does vary with s mar . Therefore, we expect a total computational complexity of O ( m 2 ‖ S mar ‖ ‖ S,ep ‖)
for updating one cluster S mar . How quickly the algorithm converges is more difficult to estimate. In the next section, however, we address this topic on the basis of a toy problem.

To conclude this section, we remark that when the LP-problem is not tractable, one can always leave out as many constraints as needed, paying the price of getting looser bounds.