The auction algorithm for assignment and shortest path problems

The auction algorithm is an intuitive method for solving the classical assignment problem. It outperforms substantially its main competitors for important types of problems, both in theory and in practice, and is also naturally well suited for parallel computation. The algorithm represents a significant departure from the cost improvement idea that underlies primal simplex and dual ascent methods; at any one iteration, it may reduce both the primal and the dual cost, although in the end it does find an optimal primal solution. This tutorial paper derives the algorithm from first principles, explains its computational properties, and briefly discusses its extensions to other types of network flow problems, with a special emphasis on the shortest path problem. An extensive discussion may be found in the author’s textbook and survey paper.