{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T00:32:06Z","timestamp":1775521926750,"version":"3.50.1"},"reference-count":44,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2013,10,3]],"date-time":"2013-10-03T00:00:00Z","timestamp":1380758400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The stable marriage (SM) problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools or, more generally, to any two-sided market. In the classical formulation, n men and n women express their preferences (via a strict total order) over the members of the other sex. Solving an SM problem means finding a stable marriage where stability is an envy-free notion: no man and woman who are not married to each other would both prefer each other to their partners or to being single. We consider both the classical stable marriage problem and one of its useful variations (denoted SMTI (Stable Marriage with Ties and Incomplete lists)) where the men and women express their preferences in the form of an incomplete preference list with ties over a subset of the members of the other sex. Matchings are permitted only with people who appear in these preference lists, and we try to find a stable matching that marries as many people as possible. Whilst the SM problem is polynomial to solve, the SMTI problem is NP-hard. We propose to tackle both problems via a local search approach, which exploits properties of the problems to reduce the size of the neighborhood and to make local moves efficiently. We empirically evaluate our algorithm for SM problems by measuring its runtime behavior and its ability to sample the lattice of all possible stable marriages. We evaluate our algorithm for SMTI problems in terms of both its runtime behavior and its ability to find a maximum cardinality stable marriage. Experimental results suggest that for SM problems, the number of steps of our algorithm grows only as O(n log(n)), and that it samples very well the set of all stable marriages. It is thus a fair and efficient approach to generate stable marriages. Furthermore, our approach for SMTI problems is able to solve large problems, quickly returning stable matchings of large and often optimal size, despite the NP-hardness of this problem.<\/jats:p>","DOI":"10.3390\/a6040591","type":"journal-article","created":{"date-parts":[[2013,10,3]],"date-time":"2013-10-03T11:49:19Z","timestamp":1380800959000},"page":"591-617","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["Local Search Approaches in Stable Matching Problems"],"prefix":"10.3390","volume":"6","author":[{"given":"Mirco","family":"Gelain","sequence":"first","affiliation":[{"name":"University of Padova, Padova 35131, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Pini","sequence":"additional","affiliation":[{"name":"University of Padova, Padova 35131, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesca","family":"Rossi","sequence":"additional","affiliation":[{"name":"University of Padova, Padova 35131, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Venable","sequence":"additional","affiliation":[{"name":"Tulane University and IHMC, New Orleans, LA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toby","family":"Walsh","sequence":"additional","affiliation":[{"name":"NICTA and UNSW, Sydney, NSW 1466, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2013,10,3]]},"reference":[{"key":"ref_1","unstructured":"Gusfield, D., and Irving, R.W. (1989). The Stable Marriage Problem: Structure and Algorithms, MIT Press."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","article-title":"College admissions and the stability of marriage","volume":"69","author":"Gale","year":"1962","journal-title":"Am. Math. Mon."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"425","DOI":"10.2307\/1913160","article-title":"On the allocation of residents to rural hospitals: A general property of two-sided matching markets","volume":"54","author":"Roth","year":"1986","journal-title":"Econometrica"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0304-3975(01)00206-7","article-title":"Hard variants of stable marriage","volume":"276","author":"Manlove","year":"2002","journal-title":"Theor. Comput. Sci."},{"key":"ref_5","unstructured":"Knuth, D.E. (1976). Marriages Stables, Les Presses."},{"key":"ref_6","unstructured":"Gent, I.P., and Prosser, P. (, January July). An empirical study of the stable marriage problem with ties and incomplete lists. Proceedings of ECAI 2002, Lyon, France."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Gelain, M., Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (, January August). Local search algorithms on the stable marriage problem: Experimental studies. Proceedings of ECAI 2010, Lisbon, Portugal.","DOI":"10.3233\/978-1-60750-606-5-1085"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Gelain, M., Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (, January August). Local search for stable marriage problems with ties and incomplete lists. Proceedings of PRICAI 2010, LNCS 6230, Daegu, Korea.","DOI":"10.1007\/978-3-642-15246-7_9"},{"key":"ref_9","unstructured":"Gelain, M., Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (, January May). Procedural fairness in stable marriage problems. Proceedings of AAMAS 2011, Taipei, Taiwan."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1137\/0216010","article-title":"Three fast algorithms for four problems in stable marriage","volume":"16","author":"Gusfield","year":"1987","journal-title":"SIAM Journal on Computing"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1145\/28869.28871","article-title":"An efficient algorithm for the \u201coptimal\u201d stable marriage","volume":"34","author":"Irving","year":"1987","journal-title":"J. ACM"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1475","DOI":"10.2307\/2938326","article-title":"Random paths to stability in two-sided matching","volume":"58","author":"Roth","year":"1990","journal-title":"Econometrica"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1016\/S0304-3975(03)00321-9","article-title":"Approximability results for stable marriage problems with ties","volume":"306","author":"Irving","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_14","unstructured":"Scott, S. (2005). A study of stable marriage problems with ties. [Ph.D. Thesis, University of Glasgow]."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Iwama, K., Miyazaki, S., and Yanagisawa, H. (, January July). Randomized Approximation of the Stable Marriage Problem. Proceedings of COCOON 2003, LNCS 2697, Big Sky, MT, USA.","DOI":"10.1007\/3-540-45071-8_35"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Iwama, K., Miyazaki, S., and Yanagisawa, H. (2007). Improved approximation results for the stable marriage problem. ACM Trans. Alg., 3.","DOI":"10.1145\/1273340.1273346"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Iwama, K., Miyazaki, S., and Okamoto, K. (, January July). A (2-c(log N\/N))-Approximation Algorithm for the Stable Marriage Problem. Proceedings of Algorithm Theory\u2014SWAT 2004, LNCS 3111, Humlebaek, Denmark.","DOI":"10.1007\/978-3-540-27810-8_30"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Iwama, K., Miyazaki, S., and Yanagisawa, H. (2012). A 25\/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties. Algorithmica.","DOI":"10.1007\/s00453-012-9699-2"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s10878-007-9133-x","article-title":"Approximation algorithms for hard variants of the stable marriage and hospitals\/residents problems","volume":"16","author":"Manlove","year":"2008","journal-title":"J. Comb. Optim"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Iwama, K., Miyazaki, S., and Yamauchi, N. (, January January). A 1.875: approximation algorithm for the stable marriage problem. Proceedings of SODA 2007, New Orleans, Louisiana, USA.","DOI":"10.1007\/s00453-007-9101-y"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00453-009-9371-7","article-title":"Better and Simpler Approximation Algorithms for the Stable Marriage Problem","volume":"60","year":"2011","journal-title":"Algorithmica"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"McDermid, E. (, January July). A 3\/2-approximation algorithm for general stable marriage. Proceedings of ICALP 2009, LNCS 5555, Rhodes, Greece.","DOI":"10.1007\/978-3-642-02927-1_57"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Manlove, D.F. (2013). Algorithmics of Matching Under Preferences, World Scientific Publishing.","DOI":"10.1142\/8591"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (1999). Parametrized Complexity, Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1007\/s00453-009-9326-z","article-title":"Parameterized complexity and local search approaches for the stable marriage problem with ties","volume":"58","author":"Marx","year":"2010","journal-title":"Algorithmica"},{"key":"ref_26","first-page":"7","article-title":"Local search","volume":"3","author":"Marx","year":"2008","journal-title":"Parameterized Complexity News"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.disopt.2010.07.004","article-title":"Stable assignment with couples: Parameterized complexity and local search","volume":"8","author":"Marx","year":"2011","journal-title":"Discrete Optimization"},{"key":"ref_28","unstructured":"Laburthe, F. Choco, a constraint programming kernel for solving combinatorial optimization problems. Available online: http:\/\/choco-solver.net."},{"key":"ref_29","unstructured":"Gent, I.P., Prosser, P., Smith, B.M., and Walsh, T. (, January May). Sat encodings of the stable marriage problem with ties and incomplete lists. Proceedings of SAT 2002, Cincinnati, Ohio, USA."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Brito, I., and Meseguer, P. (, January September). Distributed stable matching problems with ties and incomplete lists. Proceedings of CP 2006, LNCS 4204, Nantes, France.","DOI":"10.1007\/11889205_49"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1.2:1","DOI":"10.1145\/1498698.1537595","article-title":"Finding large stable matchings","volume":"14","author":"Irving","year":"2009","journal-title":"J. Exp. Algorithmics"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1828","DOI":"10.1016\/j.tcs.2010.02.003","article-title":"Size versus stability in the marriage problem","volume":"411","author":"Manlove","year":"2010","journal-title":"Theo. Com. Sci."},{"key":"ref_33","unstructured":"Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (, January May). Manipulation and gender neutrality in stable marriage procedures. Proceedings of AAMAS 2009, Budapest, Hungary."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/s10458-010-9121-x","article-title":"Manipulation complexity and gender neutrality in stable marriage procedures","volume":"22","author":"Pini","year":"2011","journal-title":"J. Aut. Agents Multi-Agent Sys."},{"key":"ref_35","unstructured":"Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (, January January). Stability in Matching Problems with Weighted Preferences. Proceedings of ICAART 2011, Rome, Italy."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (, January July). Weights in stable marriage problems increase manipulation opportunities. Proceedings of TARK 2011, Groningen, The Netherlands.","DOI":"10.1145\/2000378.2000402"},{"key":"ref_37","unstructured":"Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (2012). Agents and Artificial Intelligence 2011 - ICAART 2011 - Revised Selected Papers, CCIS 271."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Gelain, M., Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. Male optimal and unique stable marriages with partially ordered preferences. Proceedings of CARE 2009\/2010, LNAI 6066, Melbourne, Australia.","DOI":"10.1007\/978-3-642-22427-0_4"},{"key":"ref_39","unstructured":"Gelain, M., Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (, January May). Male optimality and uniqueness in stable marriage problems with partial orders - Extended abstract. Proceedings of AAMAS 2010, Toronto, Canada."},{"key":"ref_40","unstructured":"Bhatnagar, N., Greenberg, S., and Randall, D. (, January January). Sampling stable marriages: why spouse-swapping won\u2019t work. Proceedings of SODA 2008, San Francisco, CA, USA."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Iwama, K., Manlove, D.F., Miyazaki, S., and Morita, Y. (, January July). Stable marriage with incomplete lists and ties. Proceedings of ICALP 1999, LNCS 1644, Prague, Czech Republic.","DOI":"10.1007\/3-540-48523-6_41"},{"key":"ref_42","unstructured":"Rossi, F., and Van Beek, P. (2006). Handbook of Constraint Programming, Elsevier."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"501","DOI":"10.3406\/ecoap.1952.3831","article-title":"Les th\u00e9ories de l\u2019int\u00e9r\u00eat g\u00e9n\u00e9ral et le probl\u00e8me logique de l\u2019agr\u00e9gation","volume":"5","author":"Guilbauld","year":"1952","journal-title":"\u00c9conomie Appliqu\u00e9e"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1007\/s00453-009-9307-2","article-title":"Understanding the generalized median stable matching","volume":"58","author":"Cheng","year":"2010","journal-title":"Algorithmica"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/4\/591\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:49:41Z","timestamp":1760219381000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/4\/591"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,3]]},"references-count":44,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2013,12]]}},"alternative-id":["a6040591"],"URL":"https:\/\/doi.org\/10.3390\/a6040591","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,3]]}}}