The Auction Algorithm for Assignment and Other Network Flow Problems: A Tutorial

Abstract

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. I derive the algorithm from first principles, explain its computational properties, and discuss its extensions to transportation and transshipment problems.