KJCKorea
Journal Central

This paper proposes a simplified algorithm devised to obtain optimal solution to the marriage problem. In solving this problem, the most widely resorted to is the Gale-Shapley algorithm with the time complexity of O(│V│2│E│)The proposed algorithm on the other hand firstly constructs a Pij matrix of inter-preference sum both sexes’ preference over the opposite sex. Secondly, it selects minPi from each row to establish│P.j│≥ 2, j∈S ,│P.j │= 1 , j∈H ,│P.j │= 0 , j∈T. Finally, it shifts min{minPST,PSH+PHT} for minPST of S→T and PSH+PHT ,PHT<minPST of S→H, H→T . The proposed algorithm has not only improved the Gale-Shapley’s algorithm’s complexity of O(│V│2│E│)to O(│V│2) but also proved its extendable use on unbalanced marriage problems.

Marriage problem, Minimumweight matching, Maximummatching, Preference