Solution of the optimal assignment problem by diagonal scaling algorithms
This provides a novel, parallelizable preprocessing method for large dense optimal assignment problems, reducing memory requirements.
The authors show that the optimal assignment problem can be solved via entropy maximization as a deformation parameter tends to infinity, enabling the use of the Sinkhorn algorithm as a parallelizable preprocessing step to reduce large dense instances by deleting non-optimal entries, making them solvable with limited memory.
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.