For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A -Approximation Algorithm for the Stable Marriage Problem
Kazuo IWAMA Shuichi MIYAZAKI Kazuya OKAMOTO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2006/08/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing)
stable marriage problem, incomplete lists, ties, approximation algorithms, local search,
Full Text: PDF(225.3KB)>>
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.