Optimization in Matching Problem

Правка en1, от 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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский trailblazer995 2019-11-05 00:15:40 453 Initial revision (published)