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
![](https://test.transtutors.com/qimg/d1ba8bed-51e7-47a6-a441-64222f2ca27c.png)
![](https://test.transtutors.com/qimg/83248670-a86b-4f0a-88e3-930bc59ebb5f.png)