article

Stable assignment with couples: Parameterized complexity and local search

Authors:

Ildikó SchlotterAuthors Info & Claims

Discrete Optimization, Volume 8, Issue 1

Pages 25 - 40

https://doi.org/10.1016/j.disopt.2010.07.004

Published: 01 February 2011 Publication History

Abstract

We study the Hospitals/Residents with Couples problem, a variant of the classical Stable Marriage problem. This is the extension of the Hospitals/Residents problem where residents are allowed to form pairs and submit joint rankings over hospitals. We use the framework of parameterized complexity, considering the number of couples as a parameter. We also apply a local search approach, and examine the possibilities for giving FPT algorithms applicable in this context. Furthermore, we also investigate the matching problem containing couples that is the simplified version of the Hospitals/Residents with Couples problem modeling the case when no preferences are given.

References

[1]

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

[2]

Roth, A.E., The evolution of the labor market for medical interns and residents: a case study in game theory. J. Political Econom. v92. 991-1016.

[3]

Roth, A.E. and Sotomayor, M., . In: Econometric Society Monographs, vol. 18. Cambridge University Press, Cambridge, MA.

[4]

P.A. Robards, Applying Two-Sided Matching Processes to the United States Navy Enlisted Assignment Process, Ph.D. Thesis, Naval Postgraduate School Monterey CA, 2001.

[5]

D.F. Manlove, Stable marriage with ties and unacceptable partners, Technical Report, University of Glasgow, Department of Computing Science, 1999.

[6]

Manlove, D.F., Irving, R.W., Iwama, K., Miyazaki, S. and Morita, Y., Hard variants of stable marriage. Theor. Comput. Sci. v276 i1-2. 261-279.

[7]

An efficient algorithm for the stable roommates problem. J. Algorithms. v6 i4. 577-595.

[8]

Irving, R.W. and Manlove, D.F., The stable roommates problem with ties. J. Algorithms. v43 i1. 85-105.

[9]

Roth, A.E., A natural experiment in the organization of entry-level labor markets: regional markets for new physicians and surgeons in the United Kingdom. American Economic Review. v81 i3. 415-440.

[10]

Blair, C., The lattice structure of the set of stable matchings with multiple partners. Math. Oper. Res. v13 i4. 619-628.

[11]

A theory of stability in many-to-many matching markets. Theor. Econ. v1 i2. 233-273.

[12]

The redesign of the matching market for American physicians: some engineering aspects of economic design. American Economic Review. v89 i4. 748-780.

[13]

Ronn, E., NP-complete stable matching problems. J. Algorithms. v11 i2. 285-304.

[14]

Klaus, B. and Klijn, F., Stable matchings and preferences of couples. J. Econom. Theory. v121 i1. 75-106.

[15]

Cantala, D., Matching markets: the particular case of couples. Economics Bulletin. v3 i45. 1-11.

[16]

Dutta, B. and Massó, J., Stability of matchings when individuals have preferences over colleagues. J. Econom. Theory. v75 i2. 464-475.

[17]

McDermid, E.J. and Manlove, D.F., Keeping partners together: algorithmic results for the hospitals/residents problem with couples. J. Combin. Optim. v19 i3. 279-303.

[18]

Downey, R.G. and Fellows, M.R., . In: Monographs in Computer Science, Springer-Verlag, New York.

Digital Library

[19]

. In: Aarts, E.H.L., Lenstra, J.K. (Eds.), Local Search in Combinatorial Optimization, Princeton University Press, Princeton, NJ.

Digital Library

[20]

Marx, D., Local search. In: Parameterized Complexity News, vol. 3. pp. 7-8.

[21]

Khuller, S., Bhatia, R. and Pless, R., On local search and placement of meters in networks. In: SODA'00: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. pp. 319-328.

[22]

Krokhin, A. and Marx, D., On the hardness of losing weight. In: Lecture Notes in Computer Science, vol. 5125. Springer, Berlin. pp. 662-673.

[23]

Marx, D., Searching the k-change neighborhood for TSP is W{1}-hard. Oper. Res. Lett. v36 i1. 31-36.

[24]

A parameterized view on matroid optimization problems. Theor. Comput. Sci. v410 i44. 4471-4479.

[25]

Niedermeier, R., . In: Oxford Lecture Series in Mathematics and its Applications, vol. 31. Oxford University Press, Oxford.

[26]

Flum, J. and Grohe, M., . In: Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, New York.

Digital Library

[27]

Glass, C.A. and Kellerer, H., Parallel machine scheduling with job assignment restrictions. Nav. Res. Logist. v54 i3. 250-257.

[28]

P. Biró, E.J. McDermid, Matching with sizes (or scheduling with processing set restrictions), Technical Report TR-2010-307, University of Glasgow, Department of Computing Science, 2010.

[29]

Leung, J.Y.-T. and Li, C.-L., Scheduling with processing set restrictions: a survey. Int. J. Prod. Econ. v116. 251-262.

[30]

Gale, D. and Sotomayor, M., Some remarks on the stable matching problem. Discrete Appl. Math. v11 i3. 223-232.

[31]

Alon, N., Yuster, R. and Zwick, U., Color-coding. J. ACM. v42 i4. 844-856.

Cited By

Csáji GManlove DMcBride ITrimble JLarson K(2024)Couples can be tractableProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/302(2731-2739)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/302
Cheng CRosenbaum W(2023)Stable Matchings with Restricted Preferences: Structure and ComplexityACM Transactions on Economics and Computation10.1145/356555810:3(1-45)Online publication date: 15-Feb-2023
https://dl.acm.org/doi/10.1145/3565558
Limaye G(2023)Envy-freeness and relaxed stability for lower-quotasDiscrete Applied Mathematics10.1016/j.dam.2023.05.011337:C(288-302)Online publication date: 15-Oct-2023
https://dl.acm.org/doi/10.1016/j.dam.2023.05.011
Show More Cited By

Stable assignment with couples: Parameterized complexity and local search
1. Theory of computation

Recommendations

Stable Assignment with Couples: Parameterized Complexity and Local Search
Parameterized and Exact Computation

We study the Hospitals/Residents with Couples problem, a variant of the classical Stable Marriage problem. This is the extension of the Hospitals/Residents problem where residents are allowed to form pairs and submit joint rankings over hospitals. We ...
Matching couples with Scarf's algorithm

Scarf's algorithm (Scarf, H. E. Econometrica 35, 50---69 1967) provides fractional core elements for NTU-games. Biró and Fleiner [4] showed that Scarf's algorithm can be extended for capacitated NTU-games. In this setting agents can be involved in more ...
On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization)

Stable Marriage is a fundamental problem to both computer science and economics. Four well-known NP-hard optimization versions of this problem are the Sex-Equal Stable Marriage (SESMI), Balanced Stable Marriage (BSMI), max-Stable Marriage with Ties (max-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Optimization

Discrete Optimization Volume 8, Issue 1

February, 2011

146 pages

ISSN:1572-5286

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2010.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 February 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Csáji GManlove DMcBride ITrimble JLarson K(2024)Couples can be tractableProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/302(2731-2739)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/302
Cheng CRosenbaum W(2023)Stable Matchings with Restricted Preferences: Structure and ComplexityACM Transactions on Economics and Computation10.1145/356555810:3(1-45)Online publication date: 15-Feb-2023
https://dl.acm.org/doi/10.1145/3565558
Limaye G(2023)Envy-freeness and relaxed stability for lower-quotasDiscrete Applied Mathematics10.1016/j.dam.2023.05.011337:C(288-302)Online publication date: 15-Oct-2023
https://dl.acm.org/doi/10.1016/j.dam.2023.05.011
Boehmer NHeeger K(2022)A Fine-grained View on Stable Many-to-one Matching Problems with Lower and Upper QuotasACM Transactions on Economics and Computation10.1145/354660510:2(1-53)Online publication date: 7-Oct-2022
https://dl.acm.org/doi/10.1145/3546605
Kratsch SWahlströM M(2020)Representative Sets and Irrelevant VerticesJournal of the ACM10.1145/339088767:3(1-50)Online publication date: 2-Jun-2020
https://dl.acm.org/doi/10.1145/3390887
Bredereck RChen JFinnendahl UNiedermeier R(2020)Stable roommates with narcissistic, single-peaked, and single-crossing preferencesAutonomous Agents and Multi-Agent Systems10.1007/s10458-020-09470-x34:2Online publication date: 11-Sep-2020
https://dl.acm.org/doi/10.1007/s10458-020-09470-x
Boehmer NHeeger K(2020)A Fine-Grained View on Stable Many-To-One Matching Problems with Lower and Upper QuotasWeb and Internet Economics10.1007/978-3-030-64946-3_3(31-44)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64946-3_3
Fomin FGaspers SLokshtanov DSaurabh S(2019)Exact Algorithms via Monotone Local SearchJournal of the ACM10.1145/328417666:2(1-23)Online publication date: 8-Mar-2019
https://dl.acm.org/doi/10.1145/3284176
Gupta SRoy SSaurabh SZehavi M(2019)Balanced Stable Marriage: How Close Is Close Enough?Algorithms and Data Structures10.1007/978-3-030-24766-9_31(423-437)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-24766-9_31
Gupta SRoy S(2018)Stable Matching GamesAlgorithmica10.1007/s00453-017-0382-580:9(2551-2573)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s00453-017-0382-5
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents