Auction algorithms for network flow problems: A tutorial introduction (Q1202585)

The auction algorithm for networks flow problems is motivated by a real auction where persons compete for objects by iteratively raising the prices of these objects through competitive bidding. In the auction algorithm the bidding is controlled by an minimum \(\varepsilon\)-increase in every step and the procedure finishes if a feasible solution is at hand. After describing the basic auction algorithm and some variants of it, the survey paper of Bertsekas shows how the method can be applied to the problems of linear network flows, shortest paths, assignments, maximum flows, transportation flows and transshipment flows. The paper contains a large number of examples and figures which make it easy for the reader to understand the ideas of the auction approach.