{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T05:34:39Z","timestamp":1777440879861,"version":"3.51.4"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,8,11]],"date-time":"2016-08-11T00:00:00Z","timestamp":1470873600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/K010042\/1 and EP\/N508792\/1"],"award-info":[{"award-number":["EP\/K010042\/1 and EP\/N508792\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Scottish Informatics and Computer Science Alliance","award":["SICSA Prize PhD Studentship"],"award-info":[{"award-number":["SICSA Prize PhD Studentship"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1007\/s10601-016-9249-7","type":"journal-article","created":{"date-parts":[[2016,8,11]],"date-time":"2016-08-11T00:53:28Z","timestamp":1470876808000},"page":"50-72","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["\u201cAlmost-stable\u201d matchings in the Hospitals \/ Residents problem with Couples"],"prefix":"10.1007","volume":"22","author":[{"given":"David F.","family":"Manlove","sequence":"first","affiliation":[]},{"given":"Iain","family":"McBride","sequence":"additional","affiliation":[]},{"given":"James","family":"Trimble","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,8,11]]},"reference":[{"key":"9249_CR1","unstructured":"Abraham, D.J., Bir\u00f3, P., & Manlove, D.F (2006). \u201cAlmost stable\u201d matchings in the Roommates problem. In Proceedings of WAOA \u201905: the 3rd Workshop on Approximation and Online Algorithms, volume 3879 of Lecture Notes in Computer Science (pp. 1\u201314). Springer."},{"key":"9249_CR2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0166-218X(96)89151-7","volume":"68","author":"B Aldershof","year":"1996","unstructured":"Aldershof, B., & Carducci, O.M. (1996). Stable matching with couples. Discrete Applied Mathematics, 68, 203\u2013207.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"9249_CR3","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1006\/jeth.1998.2469","volume":"84","author":"M Balinski","year":"1999","unstructured":"Balinski, M., & S\u00f6nmez, T. (1999). A tale of two mechanisms: student placement. Journal of Economic Theory, 84(1), 73\u201394.","journal-title":"Journal of Economic Theory"},{"key":"9249_CR4","unstructured":"Bir\u00f3, P. (2008). Student admissions in Hungary as Gale and Shapley envisaged. Technical Report TR-2008-291. University of Glasgow, Department of Computing Science."},{"key":"9249_CR5","doi-asserted-by":"crossref","unstructured":"Bir\u00f3, P., Irving, R.W., & Schlotter, I. (2011). Stable matching with couples: an empirical study. ACM Journal of Experimental Algorithmics, 16. Section 1, article 2.","DOI":"10.1145\/1963190.1970372"},{"key":"9249_CR6","doi-asserted-by":"crossref","unstructured":"Bir\u00f3, P., & Klijn, F. (2013). Matching with couples: a multidisciplinary survey. International Game Theory Review, 15(2). article number 1340008.","DOI":"10.1142\/S0219198913400082"},{"key":"9249_CR7","unstructured":"Bir\u00f3, P., Manlove, D.F., & McBride, I. (2014). The Hospitals \/ Residents problem with couples: complexity and integer programming models. In Proceedings of SEA '14: the 8th Symposium on Experimental Algorithms, volume 8504 of Lecture Notes in Computer Science (pp. 10\u201321). Springer."},{"key":"9249_CR8","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/j.tcs.2012.01.022","volume":"432","author":"P Bir\u00f3","year":"2012","unstructured":"Bir\u00f3, P., Manlove, D.F., & McDermid, E.J (2012). \u201cAlmost-stable\u201d matchings in the Roommates problem with bounded preference lists. Theoretical Computer Science, 432, 10\u201320.","journal-title":"Theoretical Computer Science"},{"key":"9249_CR9","doi-asserted-by":"crossref","first-page":"1828","DOI":"10.1016\/j.tcs.2010.02.003","volume":"411","author":"P Bir\u00f3","year":"2010","unstructured":"Bir\u00f3, P., Manlove, D.F., & Mittal, S. (2010). Size versus stability in the marriage problem. Theoretical Computer Science, 411, 1828\u20131841.","journal-title":"Theoretical Computer Science"},{"key":"9249_CR10","unstructured":"Drummond, J., Perrault, A., & Bacchus, F. (2015). SAT is an effective and complete method for solving stable matching problems with couples. In Proceedings of IJCAI \u201915: the Twenty-fourth International Joint Conference on Artificial Intelligence (pp. 518\u2013525). AAAI Press."},{"issue":"3\u20134","key":"9249_CR11","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/s00182-007-0081-6","volume":"36","author":"K Eriksson","year":"2008","unstructured":"Eriksson, K., & H\u00e4ggstr\u00f6m, O. (2008). Instability of matchings in decentralized markets with various preference structures. International Journal of Game Theory, 36 (3\u20134), 409\u2013420.","journal-title":"International Journal of Game Theory"},{"issue":"1","key":"9249_CR12","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1007\/s00453-009-9353-9","volume":"58","author":"P Flor\u00e9en","year":"2010","unstructured":"Flor\u00e9en, P., Kaski, P., Polishchuk, V., & Suomela, J. (2010). Almost stable matchings by truncating the Gale-Shapley algorithm. Algorithmica, 58(1), 102\u2013118.","journal-title":"Algorithmica"},{"key":"9249_CR13","doi-asserted-by":"crossref","first-page":"9","DOI":"10.2307\/2312726","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., & Shapley, L.S. (1962). College admissions and the stability of marriage. American Mathematical Monthly, 69, 9\u201315.","journal-title":"American Mathematical Monthly"},{"key":"9249_CR14","doi-asserted-by":"crossref","unstructured":"Gent, I.P., Irving, R.W., Manlove, D.F., Prosser, P., & Smith, B.M. (2001). A constraint programming approach to the stable marriage problem. In Proceedings of CP \u201901: the 7th International Conference on Principles and Practice of Constraint Programming, volume 2239 of Lecture Notes in Computer Science (pp. 225\u2013239). Springer.","DOI":"10.1007\/3-540-45578-7_16"},{"key":"9249_CR15","unstructured":"Gusfield, D., & McDermid, R.W (1989). The stable marriage problem: structure and algorithms. MIT Press."},{"issue":"18","key":"9249_CR16","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1016\/j.ipl.2009.06.008","volume":"109","author":"K Hamada","year":"2009","unstructured":"Hamada, K., Iwama, K., & Miyazaki, S. (2009). An improved approximation lower bound for finding almost stable stable maximum matchings. Information Processing Letters, 109(18), 1036\u20131040.","journal-title":"Information Processing Letters"},{"issue":"1","key":"9249_CR17","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1007\/s00453-014-9951-z","volume":"74","author":"K Hamada","year":"2016","unstructured":"Hamada, K., Iwama, K., & Miyazaki, S. (2016). The hospitals\/residents problem with lower quotas. Algorithmica, 74(1), 440\u2013465.","journal-title":"Algorithmica"},{"key":"9249_CR18","unstructured":"Hinder, O. (2015). The stable matching linear program and an approximate rural hospital theorem with couples. In Proceedings of WINE '15: the 11th Conference on Web and Internet Economics, volume 9470 of Lecture Notes in Computer Science (pp. 433). Springer. Full version available from http:\/\/stanford.edu\/ohinder\/stability-and-lp\/working-paper.pdf ."},{"key":"9249_CR19","doi-asserted-by":"crossref","unstructured":"Irving, R.W. (1998). Matching medical students to pairs of hospitals: a new variation on a well-known theme. In Proceedings of ESA \u201998: the 6th Annual European Symposium on Algorithms, volume 1461 of Lecture Notes in Computer Science (pp. 381\u2013392). Springer.","DOI":"10.1007\/3-540-68530-8_32"},{"key":"9249_CR20","doi-asserted-by":"crossref","unstructured":"Manlove, D.F (2013). Algorithmics of Matching Under Preferences. World Scientific.","DOI":"10.1142\/8591"},{"key":"9249_CR21","unstructured":"Manlove, D.F., O\u2019Malley, G., Prosser, P., & Unsworth, C. (2007). A constraint programming approach to the hospitals \/ residents problem. In Proceedings of CP-AI-OR 2007: the 4th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization, volume 4510 of Lecture Notes in Computer Science (pp. 155\u2013170). Springer."},{"key":"9249_CR22","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.disopt.2010.07.004","volume":"8","author":"D Marx","year":"2011","unstructured":"Marx, D., & Schlotter, I. (2011). Stable assignment with couples: parameterized complexity and local search. Discrete Optimization, 8, 25\u201340.","journal-title":"Discrete Optimization"},{"key":"9249_CR23","unstructured":"McBride, I. (2015). Complexity and integer programming models for generalisations of the hospitals \/ residents problem. PhD thesis, School of Computing Science, University of Glasgow."},{"issue":"3","key":"9249_CR24","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s10878-009-9257-2","volume":"19","author":"EJ McDermid","year":"2010","unstructured":"McDermid, E.J., & Manlove, D.F. (2010). Keeping partners together: algorithmic results for the hospitals \/ residents problem with couples. Journal of Combinatorial Optimization, 19(3), 279\u2013303.","journal-title":"Journal of Combinatorial Optimization"},{"key":"9249_CR25","unstructured":"Ng, C., & Hirschberg, D.S. (1988). Complexity of the stable marriage and stable roommate problem in three dimensions. Technical Report UCI-ICS 88\u201328, Department of Information and Computing Science, University of California, Irvine."},{"key":"9249_CR26","doi-asserted-by":"crossref","unstructured":"Nguyen, T., & Vohra, R. (2015). Near feasible stable matchings. In Proceedings of EC \u201915: the Sixteenth ACM Conference on Economics and Computation (pp 41\u201342). ACM.","DOI":"10.1145\/2764468.2764471"},{"key":"9249_CR27","unstructured":"Perrault, A., Drummond, J., & Bacchus, F. (2015). Exploring strategy-proofness, uniqueness, and Pareto-optimality for the stable matching problem with couples. Technical Report arxiv:1505.03463, Computing Research Repository, Cornell University Library. Available from http:\/\/arxiv.org\/abs\/1505.03463 ."},{"key":"9249_CR28","unstructured":"Robards, P.A. (2001). Applying two-sided matching processes to the United States Navy enlisted assignment process. Master\u2019s thesis, Naval Postgraduate School, Monterey, CA."},{"issue":"2","key":"9249_CR29","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/s100580050009","volume":"3","author":"A Romero-Medina","year":"1998","unstructured":"Romero-Medina, A. (1998). Implementation of stable solutions in a restricted matching market. Review of Economic Design, 3(2), 137\u2013147.","journal-title":"Review of Economic Design"},{"key":"9249_CR30","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0196-6774(90)90007-2","volume":"11","author":"E Ronn","year":"1990","unstructured":"Ronn, E. (1990). NP-complete stable matching problems. Journal of Algorithms, 11, 285\u2013304.","journal-title":"Journal of Algorithms"},{"issue":"6","key":"9249_CR31","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1086\/261272","volume":"92","author":"AE Roth","year":"1984","unstructured":"Roth, A.E. (1984). The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy, 92(6), 991\u20131016.","journal-title":"Journal of Political Economy"},{"key":"9249_CR32","doi-asserted-by":"crossref","first-page":"1524","DOI":"10.1126\/science.2274783","volume":"250","author":"AE Roth","year":"1990","unstructured":"Roth, A.E. (1990). New physicians: a natural experiment in market organization. Science, 250, 1524\u20131528.","journal-title":"Science"},{"key":"9249_CR33","first-page":"415","volume":"81","author":"E Roth","year":"1991","unstructured":"Roth, E (1991). A natural experiment in the organization of entry level labor markets: regional markets for new physicians and surgeons in the UK. American Economic Review, 81, 415\u2013440.","journal-title":"American Economic Review"},{"key":"9249_CR34","unstructured":"Short, M.M. (2000). Analysis of the current navy enlisted detailing process. Master\u2019s thesis, Naval Postgraduate School. Monterey, CA."},{"key":"9249_CR35","unstructured":"Soldner, M. (2014). Optimization and measurement in humanitarian operations: Addressing practical needs. PhD thesis, Georgia Institute of Technology."},{"key":"9249_CR36","unstructured":"Yang, W., Giampapa, J.A., & Sycara, K. (2003). Two-sided matching for the U.S. Navy Detailing Process with market complication. Technical Report CMU-RI-TR-03-49. Robotics Institute, Carnegie-Mellon University."},{"key":"9249_CR37","unstructured":"Canadian Resident Matching Service website. http:\/\/www.carms.ca ."},{"key":"9249_CR38","unstructured":"Central Applications Office Ireland website. http:\/\/www.cao.ie ."},{"key":"9249_CR39","unstructured":"Japan Resident Matching Program website. http:\/\/www.jrmp.jp ."},{"key":"9249_CR40","unstructured":"Matching in Practice website. http:\/\/www.matching-in-practice.eu\/ ."},{"key":"9249_CR41","unstructured":"Higher Education Allocation in Ireland - Matching in Practice Website. http:\/\/www.matching-in-practice.eu\/higher-education-in-ireland ."},{"key":"9249_CR42","unstructured":"National Resident Matching Program website. http:\/\/www.nrmp.org ."}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-016-9249-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-016-9249-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-016-9249-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T16:27:51Z","timestamp":1498321671000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-016-9249-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,11]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["9249"],"URL":"https:\/\/doi.org\/10.1007\/s10601-016-9249-7","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,11]]}}}