IEICE TRANSACTIONS on Information
A 
-Approximation Algorithm for the Stable Marriage Problem
Summary :
An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. A few approximation algorithms have been proposed with approximation ratio better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio
- Publication
- IEICE TRANSACTIONS on Information Vol.E89-D No.8 pp.2380-2387
- Publication Date
- 2006/08/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e89-d.8.2380
- Type of Manuscript
- Special Section INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing)
- 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
Kazuo IWAMA, Shuichi MIYAZAKI, Kazuya OKAMOTO, "A -Approximation Algorithm for the Stable Marriage Problem" in IEICE TRANSACTIONS on Information,
vol. E89-D, no. 8, pp. 2380-2387, August 2006, doi: 10.1093/ietisy/e89-d.8.2380.
Abstract: An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. A few approximation algorithms have been proposed with approximation ratio better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.8.2380/_p
Copy
@ARTICLE{e89-d_8_2380,
author={Kazuo IWAMA, Shuichi MIYAZAKI, Kazuya OKAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={A -Approximation Algorithm for the Stable Marriage Problem},
year={2006},
volume={E89-D},
number={8},
pages={2380-2387},
abstract={An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. A few approximation algorithms have been proposed with approximation ratio better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio
keywords={},
doi={10.1093/ietisy/e89-d.8.2380},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - A -Approximation Algorithm for the Stable Marriage Problem
T2 - IEICE TRANSACTIONS on Information
SP - 2380
EP - 2387
AU - Kazuo IWAMA
AU - Shuichi MIYAZAKI
AU - Kazuya OKAMOTO
PY - 2006
DO - 10.1093/ietisy/e89-d.8.2380
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2006
AB - An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. A few approximation algorithms have been proposed with approximation ratio better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio
ER -
English
