A parallel preprocessing for the optimal assignment problem based on diagonal scaling

Details A parallel preprocessing for the optimal assignment problem based on diagonal scaling A parallel preprocessing for the optimal assignment problem based on diagonal scaling

2011-04-19

arxiv.org/abs/1104.3830v1

Mathematics

Numerical Analysis

22 pages

Scientific paper

We present a preprocessing method, which is suitable for parallel computation, to solve large optimal assignment problems. We think of the optimal assignment problem as a limit of a deformation of an entropy maximization problem. We show that the matrix maximizing the entropy converges, as the deformation parameter goes to infinity, to a matrix whose nonzero entries are precisely the ones belonging to optimal assignments. For every value of the deformation parameter, the matrix of maximal entropy can be computed by Sinkhorn iteration. This leads to a parallel preprocessing for the optimal assignment problem, which allows to delete entries that do not belong to optimal assignments, so that the reduced problem becomes executable on a sequential machine.

Affiliated with

Also associated with

No associations

Rating

A parallel preprocessing for the optimal assignment problem based on diagonal scaling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A parallel preprocessing for the optimal assignment problem based on diagonal scaling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A parallel preprocessing for the optimal assignment problem based on diagonal scaling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-183812