research-article

Approximation algorithms for the sex-equal stable marriage problem

Authors:

Shuichi Miyazaki,

Hiroki YanagisawaAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 7, Issue 1

Article No.: 2, Pages 1 - 17

https://doi.org/10.1145/1868237.1868239

Published: 08 December 2010 Publication History

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.

References

[1]

Bonsma, P. S. 2007. Most balanced minimum cuts and partially ordered knapsack. In Proceedings of the 6th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. 17--21.

[2]

Charikar, M., and Wirth, A. 2004. Maximizing quadratic programs: extending Grothendieck's inequality. In Proceedings of the 45th Annual Symposium on Foundations of Computer Science. 54--60.

Digital Library

[3]

Feder, T. 1992. A new fixed point approach for stable networks and stable marriages. J. Comput. Syst. Sci. 45, 233--284.

Digital Library

[4]

Feder, T. 1994. Network flow and 2-satisfiability. Algorithmica 11, 291--319.

Digital Library

[5]

Gale, D., and Shapley, L. S. 1962. College admissions and the stability of marriage. Amer. Math. Monthly 69, 9--15.

[6]

Gusfield, D. 1987. Three fast algorithms for four problems in stable marriage. SIAM J. Comput. 16, 1, 111--128.

Digital Library

[7]

Gusfield, D., and Irving, R. W. 1989. The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge, MA.

Digital Library

[8]

Gusfield, D., Irving, R. W., Leather, P., and Saks, M. 1987. Every finite distributive lattice is a set of stable matchings for a small instance. J. Combin. Theory A44, 304--309.

Digital Library

[9]

Halldórsson, M. M., Irving, R. W., Iwama, K., Manlove, D. F., Miyazaki, S., Morita, Y., and Scott, S. 2003. Approximability results for stable marriage problems with ties. Theoret. Comput. Sci. 306, 431--447.

Digital Library

[10]

Irving, R. W., and Leather, P. 1986. The complexity of counting stable marriages. SIAM J. Comput. 15, 3, 655--667.

Digital Library

[11]

Irving, R. W., Leather, P., and Gusfield, D. 1987. An efficient algorithm for the ‘optimal’ stable marriage. J. ACM 34, 3, 532--543.

Digital Library

[12]

Johnson, D. S., and Niemi, K. A. 1983. On knapsacks, partitions, and a new dynamic programming technique for trees. Math. Oper. Res. 8, 1, 1--14.

Digital Library

[13]

Kato, A. 1993. Complexity of the sex-equal stable marriage problem. Japan J. Indust. Appl. Math. 10, 1--19.

[14]

Kolliopoulos, S. G., and Steiner, G. 2007. Partially ordered knapsack and applications to scheduling. Discrete Appl. Math. 155, 8, 889--897.

Digital Library

[15]

Nesterov, Y. 1998. Semidefinite relaxation and nonconvex quadratic optimization. Optimiz. Meth. Softw. 9, 141--160.

[16]

Romero-Medina, A. 2001. ‘Sex-equal’ stable matchings. Theor. Decis. 50, 197--212.

Cited By

Wu SU LKarras P(2023)k-Best Egalitarian Stable Marriages for Task AssignmentProceedings of the VLDB Endowment10.14778/3611479.361152216:11(3240-3252)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611522
Farzadmehr MCarlan VVanelslander T(2023)Contemporary challenges and AI solutions in port operations: applying Gale–Shapley algorithm to find best matchesJournal of Shipping and Trade10.1186/s41072-023-00155-88:1Online publication date: 15-Sep-2023
https://doi.org/10.1186/s41072-023-00155-8
Gupta SSaurabh SZehavi M(2022)On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization)SIAM Journal on Discrete Mathematics10.1137/19M130491X36:1(596-681)Online publication date: 9-Mar-2022
https://doi.org/10.1137/19M130491X
Show More Cited By

Index Terms

Approximation algorithms for the sex-equal stable marriage problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

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 ...
Approximation algorithms for the sex-equal stable marriage problem
WADS'07: Proceedings of the 10th international conference on Algorithms and Data Structures

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 ...
The stable marriage problem with restricted pairs

A stable matching is a complete matching of men and women such that no man and woman who are not partners both prefer each other to their actual partners under the matching. In an instance of the STABLE MARRIAGE problem, each of the n men and n women ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 7, Issue 1

November 2010

282 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1868237

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 December 2010

Accepted: 01 January 2009

Revised: 01 December 2008

Received: 01 November 2007

Published in TALG Volume 7, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

KAKENHI

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
767
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)3

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu SU LKarras P(2023)k-Best Egalitarian Stable Marriages for Task AssignmentProceedings of the VLDB Endowment10.14778/3611479.361152216:11(3240-3252)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611522
Farzadmehr MCarlan VVanelslander T(2023)Contemporary challenges and AI solutions in port operations: applying Gale–Shapley algorithm to find best matchesJournal of Shipping and Trade10.1186/s41072-023-00155-88:1Online publication date: 15-Sep-2023
https://doi.org/10.1186/s41072-023-00155-8
Gupta SSaurabh SZehavi M(2022)On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization)SIAM Journal on Discrete Mathematics10.1137/19M130491X36:1(596-681)Online publication date: 9-Mar-2022
https://doi.org/10.1137/19M130491X
Kakimura NKamiyama NKobayashi YOkamoto Y(2022)Submodular reassignment problem for reallocating agents to tasks with synergy effectsDiscrete Optimization10.1016/j.disopt.2021.10063144:P1Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.disopt.2021.100631
Martin AVenable KMattei N(2022)Behavioral Stable Marriage ProblemsDistributed Artificial Intelligence10.1007/978-3-030-94662-3_10(150-170)Online publication date: 11-Jan-2022
https://doi.org/10.1007/978-3-030-94662-3_10
Yucel FBulut E(2020)User Satisfaction Aware Maximum Utility Task Assignment in Mobile CrowdsensingComputer Networks10.1016/j.comnet.2020.107156(107156)Online publication date: Feb-2020
https://doi.org/10.1016/j.comnet.2020.107156
Tziavelis NGiannakopoulos IDoka KKoziris NKarras PWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Equitable stable matchings in quadratic timeProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3454329(457-467)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3454329
Sühr TBiega AZehlike MGummadi KChakraborty ATeredesai AKumar VLi YRosales RTerzi EKarypis G(2019)Two-Sided Fairness for Repeated Matchings in Two-Sided MarketsProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330793(3082-3092)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3292500.3330793
Viet HTrang LTuyen LChung T(2019)A shortlist-based bidirectional local search for the stable marriage problemJournal of Experimental & Theoretical Artificial Intelligence10.1080/0952813X.2019.163565532:1(147-163)Online publication date: 3-Jul-2019
https://doi.org/10.1080/0952813X.2019.1635655
Trang LViet HVan Hoai THao T(2019)A Searching for Strongly Egalitarian and Sex-Equal Stable MatchingsProceedings of the 13th International Conference on Ubiquitous Information Management and Communication (IMCOM) 201910.1007/978-3-030-19063-7_87(1100-1111)Online publication date: 23-May-2019
https://doi.org/10.1007/978-3-030-19063-7_87
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents