Computational Optimal Transport VI: On Termination the Auction Algorithm Returns an Assignment Whose Cost Is Within nε of the OptimumTextbook
The optimal assignment problem asks for a one-to-one matching of points to objects of least total cost. It is the discrete optimal transport problem between two uniform measures with the same number of atoms, and by the Birkhoff–von Neumann theorem it coincides with the Kantorovich linear program on that instance (Peyré and Cuturi, Computational Optimal…