Refining initial bounds

Max-flow computations can also be used to refine the lower and upper bounds from initial conditions if they are not tight. To get a refined lower bound for a shadow at $t = t_0$ , say $s_1$ from Fig. 11(b), let $c(S, 1) = l_1$ , $c(S, i) = u_i$ for $i \ne 1$ , $c(i, T) = u_i$ for disappearing shadows, and $c(i, T) = 0$ for the rest. After running max-flow on this network, a tighter lower bound, if there is one, is given by

$$l_1' = l_1 + \sum_ic(i, T) - \sum_if(i, T).$$ (9)

The summations are over all applicable shadows. To refine $u_1$ , let $c(S,1) = u_1$ , $c(S, i) = l_i$ for $i \ne 1$ , $c(i, T) = u_i$ for disappearing shadows and $c(i, T) = +\infty$ . After running max-flow,

$$u_1' = f(S, 1)$$ (10)

This procedure also applies to a set of shadows.