A -Approximation Algorithm for the Stable Marriage Problem

Kazuo IWAMA  Shuichi MIYAZAKI  Kazuya OKAMOTO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.8   pp.2380-2387
Publication Date: 2006/08/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.8.2380
Print ISSN: 0916-8532
Type of Manuscript: INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing)
Category: 
Keyword: 
stable marriage problem,  incomplete lists,  ties,  approximation algorithms,  local search,  

Full Text: PDF(225.3KB)>>
Buy this Article



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.