{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:12:43Z","timestamp":1760220763607,"version":"build-2065373602"},"reference-count":18,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2013,6,24]],"date-time":"2013-06-24T00:00:00Z","timestamp":1372032000000},"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>Motivated by the observation that most companies are more likely to consider job applicants referred by their employees than those who applied on their own, Arcaute and Vassilvitskii modeled a job market that integrates social networks into stable matchings in an interesting way. We call their model HR+SN because an instance of their model is an ordered pair (I, G) where I is a typical instance of the Hospital\/Residents problem (HR) and G is a graph that describes the social network (SN) of the residents in I. A matching p, of hospitals and residents has a local blocking pair (h, r) if (h, r) is a blocking pair of ii, and there is a resident r' such that r' is simultaneously an employee of h in the matching and a neighbor of r in G. Such a pair is likely to compromise the matching because the participants have access to each other through r': r can give her resume to r' who can then forward it to h. A locally stable matching is a matching with no local blocking pairs. The cardinality of the locally stable matchings of I can vary. This paper presents a variety of results on computing a locally stable matching with maximum cardinality.<\/jats:p>","DOI":"10.3390\/a6030383","type":"journal-article","created":{"date-parts":[[2013,6,24]],"date-time":"2013-06-24T13:12:06Z","timestamp":1372079526000},"page":"383-395","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Maximum Locally Stable Matchings"],"prefix":"10.3390","volume":"6","author":[{"given":"Christine","family":"Cheng","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Wisconsin-Milwaukee, 3200 N. Cramer Street, Milwaukee, WI 53211, USA"}]},{"given":"Eric","family":"McDermid","sequence":"additional","affiliation":[{"name":"21CT, 6011 West Courtyard Drive, Austin, TX 78730, USA"}]}],"member":"1968","published-online":{"date-parts":[[2013,6,24]]},"reference":[{"key":"ref_1","first-page":"220","article-title":"Social Networks and Stable Matchings in the Job Market","volume":"Volume 5929","author":"Arcaute","year":"2009","journal-title":"Proceeding of WINE \u201909: the 5th Workshop on Internet and Network Economics"},{"key":"ref_2","first-page":"113","article-title":"Local Matching Dynamics in Social Networks","volume":"Volume 6756","author":"Hoefer","year":"2011","journal-title":"Proceedings of ICALP \u201911: 39th International Colloquium on Automata, Languages and Programming"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1030","DOI":"10.1137\/06067328X","article-title":"Popular matchings","volume":"37","author":"Abraham","year":"2007","journal-title":"SIAM J. Comput."},{"key":"ref_4","first-page":"715","article-title":"Weighted Popular Matchings","volume":"Volume 4051","author":"Mestre","year":"2006","journal-title":"Proceedings of ICALP \u201906: the 33rd International Colloquium on Automata, Languages and Programming"},{"key":"ref_5","first-page":"593","article-title":"The Least-unpopularity-factor and Least-unpopularity-margin Criteria for Matching Problems with One-sided Preferences","volume":"Volume 4957","author":"McCutchen","year":"2008","journal-title":"Proceedings of LATIN \u201908: the 8th Latin-American Theoretical Informatics Symposium"},{"key":"ref_6","unstructured":"Kavitha, T., and Nasre, M. (2009, January 16\u201318). Popular Matchings with Variable Job Capacities. Proceedings of ISAAC \u201909: the 20th International Symposium on Algorithms and Computation, Honolulu, USA."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1145\/1198513.1198520","article-title":"Rank-maximal matchings","volume":"2","author":"Irving","year":"2006","journal-title":"ACM Trans. Algorithms"},{"key":"ref_8","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":"Theor. Comput. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Hoefer, M., and Wagner, L. (2012). Locally stable matching with general preferences.","DOI":"10.1007\/978-3-642-39212-2_54"},{"key":"ref_10","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_11","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0166-218X(85)90074-5","article-title":"Some remarks on the stable matching problem","volume":"11","author":"Gale","year":"1985","journal-title":"Discret. Appl. Math."},{"key":"ref_12","unstructured":"Gusfield, D., and Irving, R. (1989). The Stable Marriage Problem: Structure and Algorithms, MIT Press."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2959","DOI":"10.1016\/j.dam.2008.01.002","article-title":"The stable marriage problem with master preference lists","volume":"156","author":"Irving","year":"2008","journal-title":"Discret. Appl. Math."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M., Iwama, K., Miyazaki, S., and Yanagisawa, H. (2007). Improved approximation of the stable marriage problem. ACM Trans. Algorithms, 3:3.","DOI":"10.1145\/1273340.1273346"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Dinur, I., and Safra, S. (2002, January 21\u201324). The Importance of Being Biased. Proceedings of STOC \u201902: the 34th Symposium on the Theory of Computing, Montreal, Canada.","DOI":"10.1145\/509914.509915"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"McDermid, E. (2009, January 5\u201312). A 3\/2-approximation Algorithm for General Stable Marriage. Proceedings of ICALP \u201909: the 36th International Colloquium on Automata, Languages and Programming, Rhodes, Greece. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-642-02927-1_57"},{"key":"ref_17","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_18","unstructured":"Paluch, K. (2011, January 8\u20139). Faster and simpler approximation of stable matchings. 2011. Proceedings WAOA \u201911: the 9th Workshop on Approximation and Online Algorithms, Saarbrucken, Germany. Lecture Notes in Computer Science."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/3\/383\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:47:30Z","timestamp":1760219250000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/3\/383"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,24]]},"references-count":18,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2013,9]]}},"alternative-id":["a6030383"],"URL":"https:\/\/doi.org\/10.3390\/a6030383","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2013,6,24]]}}}