Approximation algorithms for the sex-equal stable marriage problem

• Iwama, Kazuo

  Kyoto University

• Miyazaki, Shuichi

  Kyoto University

• Yanagisawa, Hiroki

  IBM Research

Abstract

The stable marriage problem is a classical matching problem introduced by Gale and Shapley. It is known that for any instance, there exists a solution, and there is a polynomial time algorithm to find one. However, the matching obtained by this algorithm is man-optimal, that is, the matching is favorable for men but unfavorable for women, (or, if we exchange the roles of men and women, the resulting matching is woman-optimal). The sex-equal stable marriage problem, posed by Gusfield and Irving, seeks a stable matching “fair” for both genders. Specifically it seeks a stable matching with the property that the sum of the men's scores is as close as possible to that of the women's. This problem is known to be strongly NP-hard. In this paper, we give a polynomial time algorithm for finding a near optimal solution for the sex-equal stable marriage problem. Furthermore, we consider the problem of optimizing an additional criterion: among stable matchings that are near optimal in terms of the sex-equality, find a minimum egalitarian stable matching. We show that this problem is strongly NP-hard, and give a polynomial time algorithm whose approximation ratio is less than two.

Journal

• ACM Transactions on Algorithms

  ACM Transactions on Algorithms 7 (1), 1-17, 2010-11-01

  Association for Computing Machinery (ACM)

Keywords

• Mathematics (miscellaneous)

Details

• CRID: 1050001335849436032
• NII Article ID: 120006338075
• ISSN: 15496325
• ISSN: 15496333
• DOI: 10.1145/1868237.1868239
• HANDLE: 2433/226949
• Web Site: https://dl.acm.org/doi/pdf/10.1145/1868237.1868239
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN