Deriving Auction from -Relaxation) Consider the assignment problem formulated as a minimum cost flow problem We say that source i is assigned to sink j if (i, j) has positive flow. We consider a version of the -relaxation algorithm in which -relaxation iterations are organized as follows: between iterations (and also at initialization), only source nodes i can have positive surplus. Each iteration finds any unassigned source i (i.e., one with positive surplus), and performs an -relaxation iteration at i, and then takes the sink j to which i was consequently assigned and performs an -relaxation iteration at j, even if j has zero surplus. (If j has zero surplus, such an iteration will consist of just a degenerate price rise; see Exercise 7.18.) Mo
