Give an upper bound for the number of iterations of the repeat-loop in Algorithm XXXXXXXXXXif the functions b , c , and γ are integral. Foe a long time, the most popular algorithm for determining an...

Give an upper bound for the number of iterations of the repeat-loop in Algorithm 10.4.1 if the functions
b,
c, and
γ
are integral. Foe a long time, the most popular algorithm for determining an optimal circulation was not the algorithm of Klein presented here, but the so-called
out-of-kilter algorithm; see [Ful61] and [Min60]. However, that algorithm is considerably more involved; it is based on Minty’s painting lemma. We refer the interested reader to [FoFu62], [Law76], or [GoMi84] for a presentation of the out-of-kilter algorithm. It is also not polynomial in our terminology: its complexity likewise depends on the capacity constraints.