
$$\begin{array}{c c c}{{}}&{{}}&{{B}}&{{}}&{{C}}\\ {{}}&{{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}&{{H^{\alpha}\ E,\ E^{\dagger}}}\\ {{}}&{{}}&{{}}&{{}}\\ {{}}&{{}}&{{B}}&{{}}&{{C}}\\ {{}}&{{}}&{{}}&{{J\ E,\ E^{\dagger}}}&{{\ \ \Box}}\end{array}$$
$$I^{\alpha}\,\,E\,,E^{\dagger}$$

| Proof. Let Pr B C                                 | for all     | B C)[   | ; v               | KB such that B   | C              | By Theorem 4.2,   |                  |
|---------------------------------------------------|-------------|---------|-------------------|------------------|----------------|-------------------|------------------|
| the requested least upper bound is the maximum of | sub ject to | H  E ; E"         | and               |                  |                |                   |                  |
| Pr C B                                            | uC          | u ; u   | for all           | C B)[u ; u       | KB such that B | C                 | By Lemma 4.4, we |
| can equivalently maximize                         | sub ject to | I E ; E"         | and J E ; E" ). 2 |                  |                |                   |                  |

still contain min-operations that cannot be tackled by linear programming. Moreover, given

method for solving this optimization problem, we are also interested in rough idea on

the overall time complexity of computing the requested least upper bound this way. Finally,

we are interested in possible improvements to increase eciency. These topics are discussed

problem is already linear program. Otherwise, it can easily be transformed into linear

remaining outer min-operation is eliminated by introducing exactly one linear inequality

for each contained operand. In these linear inequalities, the operands of the outer minoperation are upper bounds of

To get rough idea on the time complexity of computing the requested least upper

We now wonder how to solve the generated optimization problem, since I E ; E" may
in the rest of this section.

$$I^{\alpha}\,\,\,E\,,\,E^{\dagger}$$
$$I^{\alpha}\setminus E,\,E^{\uparrow}$$
If I E ; E"does not contain any min-operations at all, then the generated optimization
program. In rst transformation step, all inner min-operations are eliminated. This can

easily be done due to the well-structuredness of I E ; E"). In second step, the only
bound this way, we must analyze the size of the generated linear programs. It is given by the number of variables, the number of linear inequalities in J E ; E"), and the num- ber of linear inequalities extracted from I E ; E"). The latter is quite worrying, since I  B ; C in Fusion seems to produce many min-operands. Moreover, I  B ; C in Fusion contains I B ; Bi), and I B ; C in Chaining contains I C; C"). So, due to this crossed dependency, the overall number of generated linear inequalities is likely to

`explode' for trees that branch very often. To avoid these problems, we introduce the auxiliary functions J J  and J  over the variables B B B). Let J  B ; C 0J  B ; C 0and J  B ; C  0where 00 and  0in Leaf C B), Chaining C B ), and Fusion C B1 B2 : : : Bk with k 1)

are given as follows:

Leaf

$$\begin{array}{c c c}{{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}\\ {{}}&{{}}&{{\alpha^{\prime}}}\\ {{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}\end{array}$$

Chaining 0 min( B; C + J C; C" Pr BjC ; B C + J C; C" Pr BjC 0 Pr BjC Pr BjC C + J C; C" Pr BjC  0 J C; C" Pr BjC 218

