A <eq200610.gif>-Approximation Algorithm for the Stable Marriage Problem

Kazuo IWAMA; Shuichi MIYAZAKI; Kazuya OKAMOTO

doi:10.1093/ietisy/e89-d.8.2380

A -Approximation Algorithm for the Stable Marriage Problem

Kazuo IWAMA, Shuichi MIYAZAKI, Kazuya OKAMOTO

Full Text Views

0

Share
Cite this

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 for an arbitrarily positive constant c, where N denotes the number of men in an input.

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

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 for an arbitrarily positive constant c, where N denotes the number of men in an input.
URL: https://globals.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 for an arbitrarily positive constant c, where N denotes the number of men in an input.},
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 for an arbitrarily positive constant c, where N denotes the number of men in an input.
ER -