The Journal of the Institute of Internet, Broadcasting and Communication (한국인터넷방송통신학회논문지)

The Institute of Internet, Broadcasting and Communication (한국인터넷방송통신학회)
권호 표지
DOI QR코드

DOI QR Code

Marriage Problem Algorithm Based on Maximum-Preferred Rank Selection Method

최대 선호도 순위선정 방법에 기반한 결혼문제 알고리즘

  • Lee, Sang-Un (Dept. of Multimedia Eng., Gangneung-Wonju National University)
  • 이상운 (강릉원주대학교 과학기술대학 멀티미디어공학과)
  • Received : 2014.01.19
  • Accepted : 2014.06.13
  • Published : 2014.06.30
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper I propose a simple optimal solution seeking algorithm to a stable marriage problem. The proposed algorithm firstly constructs an $n{\times}n$ matrix of the sum of each gender's preference of the other gender $p_{ij}$. It then selects the minimum sum preference $_{min}p_{ij}$ in the constructed matrix and deletes its corresponding row i and column j. This process is repeated until $i=0{\cap}j=0$, after which the algorithm compares initially or last chosen $_{min}p_{ij}$ its alternatives to finally determine one that yields the maximum marginal increase in preference. When applied to 7 stable marriage problems, the proposed algorithm has improved on initial solutions of existing algorithms.

본 논문은 안정된 결혼문제의 최적 해를 쉽고 빠르게 찾는 알고리즘을 제안하였다. 첫 번째로, 남성의 여성선호도와 여성의 남성 선호도 합 $p_{ij}$의 $n{\times}n$ 정방행렬 할당문제로 변환시킨다. 두 번째로, 행렬에서 최대 선호도 합(최소 값)인 $_{min}p_{ij}$를 선택하고 i행과 j열을 삭제한다. 이 과정을 $i=0{\cap}j=0$일 때까지 수행한다. 세 번째로, 가능한 최초 또는 마지막 선택 $_{min}p_{ij}$에 대해 다른 값으로 변경시 선호도를 증가시킬 수 있으면 상호 교환하는 검증 절차를 수행한다. 제안된 알고리즘을 7개의 안정된 결혼문제에 적용한 결과 기존 알고리즘의 해를 개선하는 효과를 얻었다.

Keywords

References

  1. Wikipedia, "Matching," http://en.wikipedia.org/wiki/Matching, Wikimedia Foundation Inc., 2014.
  2. T. Szabo, "Graph Theory," Institute of Technical Computer Science, Department of Computer Science, ETH, http://www.ti.inf.ethz.ch/ ew/courses/GT03/Lectures/PDF/, 2004.
  3. Wikipedia, "Assignment Problem," http://en.wikipedia. org/wiki/Assignment_problem, Wikimedia Foundation Inc., 2014.
  4. M. X. Goemans, "18,433 Combinatorial Operation: Lecture Notes on Bipartite Matching," Massachusetts Institute of Technology, http://math. mit.edu/-goemans/ 1843307/matching- notes.pdf, 2007.
  5. J. T. Eyck, 'Algorithm Analysis and Design," http://www.academic.marist.edu/-jzbv/algorithms/ TheStableMarriageProblem.htm, 2008.
  6. Wikipedia, "Stable Marriage Problem,," http://en.wikipedia.org/wiki/Stable_marriage_problem, Wikimedia Foundation Inc., 2014.
  7. Wikipedia, "Hungarian Algorithm," http://en.wikipedia.org/wiki/Hungarian_algorithm, Wikimedia Foundation Inc., 2010.
  8. L. Ntaimo, "Introduction to Mathematical Programming: Operations Research: Transportation and Assignment Problems", Vol. 1, 4th edition, by W. L. Winston and M. Venkataramanan, http://ie.tamu.edu/INEN420/ INEN420_2005Spring/ SLIDES/Chapter 7.pdf, 2005.
  9. W. Hunt, "The Stable Marriage Problem," Lane Department of Computer Science and Electrical Engineering, West Virginia University, http://www. csee.wvu.edu/-ksmani/courses/fa01/random/lecture notes/lecture5.pdf, 2004.
  10. W. Snyder, "The Linear Assignment Problem," Department of Electrical and Computer Engineering, North Carolina State University, http://www4. ncsu.edu/-wes/AssignmentProblem.pdf, 2005.
  11. R. W. Irving, "Stable Matching Problems with Exchange Restrictions," Journal of Combinatorial Optimization, Vol. 16, No. 4, pp. 344-360, Nov. 2008. https://doi.org/10.1007/s10878-008-9153-1
  12. R. W. Irving, "The Man-Exchange Stable Marriage Problem," Department of Computing Science, Research Report, TR-2004-177, University of Glasgow, UK., http://www.dcs.gla.ac.uk/-rwi/me_stable.pdf, 2004.
  13. K. Iwama, "Stable Matching Problems," http:// www.lab2.kuis.kyoto-u.ac.jp/-iwama/papers/isaac2006-3.ppt, 2006.
  14. J. H. Kim, "MAT 2106-02 Discrete Mathematics: Combinatory Theory from Marriage Problem Perspective," Department of Mathematics, Yousei University, Korea, 2001.