Optimization in Matching Problem

Revision en1, by trailblazer995, 2019-11-05 00:15:40

Hi all, i came across a real life problem where we have N workers and M jobs and edges are given for valid matching with it's weight. Maximum weight matching here can be found using Hungarian's algorithm where complexity will be O(max(N,M)^3). Here N <= 100 and M <= 2000. Can we have some optimisation here for this case such that we don't need to create dummy entries to make MxM matrix? Or is there any other solution?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English trailblazer995 2019-11-05 00:15:40 453 Initial revision (published)