holycall holycall

실험 과정에서 Maximum Weight Bipartartite Matching 을 할 필요가 있었다. 이것은 OR에서 Linear Assignment Problem (LAP) 이라고 부른다. 이 과정에서 처음 알게 된 방식이 Kuhn의 Hungarian Method [Kuhn1955] 이다. Hungarian Method는 처음으로 polynomial time에 LAP를 해결 이 알고리즘은 Munkress에 의해 개선되었고 Lawler의 구현에서는 O(n^3) 알고리즘으로 개선되었다. (n은 node 개수, m은 edge 개수) 현재 실험에서 다루고 있는 문제 (n=10^3~10^4, m = n^2) 를 Hungarian Method로 실험해 보면 시간이 정말 오래 걸려서 끝나지 않는다. :) 현재 L..