Solution of the optimal assignment problem by diagonal scaling algorithms

Abstract

We show that a solution of the optimal assignment problem can be obtained as the limit of the solution of an entropy maximization problem, as a deformation parameter tends to infinity. This allows us to apply entropy maximization algorithms to the optimal assignment problem. In particular, the Sinkhorn algorithm leads to a parallelizable method, which can be used as a preprocessing to handle large dense optimal assignment problems. This parallel preprocessing allows one to delete entries which do not belong to optimal permutations, leading to a reduced instance which becomes solvable with limited memory requirements.

24 pages

Cited by in corpus (5)

• Scaling Algorithms for Unbalanced Transport Problems
• Approximation of Optimal Transport problems with marginal moments constraints
• An explicit analysis of the entropic penalty in linear programming
• An Exploration of Learnt Representations of W Jets
• Loopy annealing belief propagation for vertex cover and matching: convergence, LP relaxation, correctness and Bethe approximation