Solution of the optimal assignment problem by diagonal scaling algorithms
From MaRDI portal
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.
This page was built for publication: Solution of the optimal assignment problem by diagonal scaling algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6224912)
