(Degenerate Price Rises) In this exercise, we consider a variation of the -relaxation method that involves degenerate price rises. A degenerate price rise changes the price of a node that currently has zero surplus to the maximum possible value that does not violate -CS with respect to the current flow vector (compare with degenerate price rises in the context of the single-node relaxation iteration where = 0, as illustrated in Fig. 6.8 of Section 6.5). Consider a variation of the -relaxation method where there are two types of iterations: (1) regular iterations, which are of the form described in the present section, and (2) degenerate iterations, which consist of a single degenerate price rise. (a) Show that if the problem is feasible and the number of degenerate iterations is bounded by a constant times the number of regular iterations, then the method terminates with a pair (x, p) satisfying -CS. (b) Show that the assumption of part (a) is essential for the validity of the method.
