IEICE TRANSACTIONS on Fundamentals
Sex-Fair Stable Marriage Problem and Its GA Solution
Summary :
In this paper we consider a sex-fair matching in the stable marriage problem. The sex-fair stable matching defined in this paper has a property that the sum of partner's ranks of individual men in their preference lists is as close as possible to the sum of partner's ranks of individual women in their preference lists. However, the sex-fair stable marriage problem is known as one of important open problems in the stable marriage problems. The main result of this paper is to propose a method for adapting a genetic algorithm (GA) to the sex-fair problem to find the sex-fair matching effectively. In the method we transform the sex-fair marriage problem into a graph problem whose decision version is shown to be NP-complete. The graph problem representation is suitable for GA application, that is, easier coding, easier and more effective definition of genetic operators. Computer experiment reports effectiveness of the GA solution.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E78-A No.6 pp.664-670
- Publication Date
- 1995/06/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section of Papers Selected from 1994 Joint Technical Conference on Circuits/Systems, Computers and Communications (JTC-CSCC '94))
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Morikazu NAKAMURA, Kenji ONAGA, Seiki KYAN, "Sex-Fair Stable Marriage Problem and Its GA Solution" in IEICE TRANSACTIONS on Fundamentals,
vol. E78-A, no. 6, pp. 664-670, June 1995, doi: .
Abstract: In this paper we consider a sex-fair matching in the stable marriage problem. The sex-fair stable matching defined in this paper has a property that the sum of partner's ranks of individual men in their preference lists is as close as possible to the sum of partner's ranks of individual women in their preference lists. However, the sex-fair stable marriage problem is known as one of important open problems in the stable marriage problems. The main result of this paper is to propose a method for adapting a genetic algorithm (GA) to the sex-fair problem to find the sex-fair matching effectively. In the method we transform the sex-fair marriage problem into a graph problem whose decision version is shown to be NP-complete. The graph problem representation is suitable for GA application, that is, easier coding, easier and more effective definition of genetic operators. Computer experiment reports effectiveness of the GA solution.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e78-a_6_664/_p
Copy
@ARTICLE{e78-a_6_664,
author={Morikazu NAKAMURA, Kenji ONAGA, Seiki KYAN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Sex-Fair Stable Marriage Problem and Its GA Solution},
year={1995},
volume={E78-A},
number={6},
pages={664-670},
abstract={In this paper we consider a sex-fair matching in the stable marriage problem. The sex-fair stable matching defined in this paper has a property that the sum of partner's ranks of individual men in their preference lists is as close as possible to the sum of partner's ranks of individual women in their preference lists. However, the sex-fair stable marriage problem is known as one of important open problems in the stable marriage problems. The main result of this paper is to propose a method for adapting a genetic algorithm (GA) to the sex-fair problem to find the sex-fair matching effectively. In the method we transform the sex-fair marriage problem into a graph problem whose decision version is shown to be NP-complete. The graph problem representation is suitable for GA application, that is, easier coding, easier and more effective definition of genetic operators. Computer experiment reports effectiveness of the GA solution.},
keywords={},
doi={},
ISSN={},
month={June},}
Copy
TY - JOUR
TI - Sex-Fair Stable Marriage Problem and Its GA Solution
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 664
EP - 670
AU - Morikazu NAKAMURA
AU - Kenji ONAGA
AU - Seiki KYAN
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E78-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 1995
AB - In this paper we consider a sex-fair matching in the stable marriage problem. The sex-fair stable matching defined in this paper has a property that the sum of partner's ranks of individual men in their preference lists is as close as possible to the sum of partner's ranks of individual women in their preference lists. However, the sex-fair stable marriage problem is known as one of important open problems in the stable marriage problems. The main result of this paper is to propose a method for adapting a genetic algorithm (GA) to the sex-fair problem to find the sex-fair matching effectively. In the method we transform the sex-fair marriage problem into a graph problem whose decision version is shown to be NP-complete. The graph problem representation is suitable for GA application, that is, easier coding, easier and more effective definition of genetic operators. Computer experiment reports effectiveness of the GA solution.
ER -
English
