Improved approximation results for the stable marriage problem

The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially we can obtain a 2-approximation algorithm. In th...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on algorithms 2007-08, Vol.3 (3), p.30
Main Authors: Halldórsson, Magnús M., Iwama, Kazuo, Miyazaki, Shuichi, Yanagisawa, Hiroki
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially we can obtain a 2-approximation algorithm. In this article, we give the first nontrivial result for approximation of factor less than two. Our algorithm achieves an approximation ratio of 2/(1 + L −2 ) for instances in which only men have ties of length at most L . When both men and women are allowed to have ties but the lengths are limited to two, then we show a ratio of 13/7(1.1052).
ISSN:1549-6325
1549-6333
DOI:10.1145/1273340.1273346