Marriage Problem Algorithm Based on Maximum-Preferred Rank Selection Method
Journal: The Journal of the Institute of Internet, Broadcasting and Communication (Vol.14, No. 3)Publication Date: 2014-06-30
Authors : Sang-Un Lee;
Page : 111-117
Keywords : Marriage problem; Minimum weight matching; Maximum matching; Preference;
Abstract
In this paper I propose a simple optimal solution seeking algorithm to a stable marriage problem. The proposed algorithm firstly constructs an n×n matrix of the sum of each gender’s preference of the other gender Pij. It then selects the minimum sum preference minPij in the constructed matrix and deletes its corresponding row i and column j. This process is repeated until i=0 ∩ j=0, after which the algorithm compares initially or last chosen minPij 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.
Other Latest Articles
- Identification and Modularization of Feature Interactions Using Feature-Feature Code Mapping
- A Proposal on Multi-transmission Mechanism of the Heterogeneous Network Environment for SMART Screen Services
- Measure and Analysis of Open-Close Frequency of Mouth and Eyes for Sleepiness Decision
- Traffic Safety System based on WEB
- Design and Component of Transportation Culture Index Evaluation System
Last modified: 2016-01-22 09:35:08