{"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":1775521926477,"version":"3.50.1"},"reference-count":22,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T00:00:00Z","timestamp":1376524800000},"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>We consider a two-sided market under incomplete preference lists with ties, where the goal is to find a maximum size stable matching. The problem is APX-hard, and a 3\/2-approximation was given by McDermid [1]. This algorithm has a non-linear running time, and, more importantly needs global knowledge of all preference lists. We present a very natural, economically reasonable, local, linear time algorithm with the same ratio, using some ideas of Paluch [2]. In this algorithm every person make decisions using only their own list, and some information asked from members of these lists (as in the case of the famous algorithm of Gale and Shapley). Some consequences to the Hospitals\/Residents problem are also discussed.<\/jats:p>","DOI":"10.3390\/a6030471","type":"journal-article","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T02:05:47Z","timestamp":1376618747000},"page":"471-484","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":47,"title":["Linear Time Local Approximation Algorithm for Maximum Stable Marriage"],"prefix":"10.3390","volume":"6","author":[{"given":"Zolt\u00e1n","family":"Kir\u00e1ly","sequence":"first","affiliation":[{"name":"Department of Computer Science and MTA-ELTE Egerv\u00e1ry Research Group, E\u00f6tv\u00f6s University, P\u00e1zm\u00e1ny P\u00e9ter s\u00e9tany 1\/C, Budapest 1117, Hungary"}]}],"member":"1968","published-online":{"date-parts":[[2013,8,15]]},"reference":[{"key":"ref_1","unstructured":"McDermid, E.J. (2009, January 5\u201312). A \n\t\t\t\t\t\t\t\t\t        \n\t\t\t\t\t\t\t\t\t          \n\t\t\t\t\t\t\t\t\t\t\t    \n\t\t\t\t\t\t\t\t\t            3\n\t\t\t\t\t\t\t\t\t            2\n\t\t\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t          \n\t\t\t\t\t\t\t\t\t        \n\t\t\t\t\t\t\t\t\t      -approximation Algorithm for General Stable Marriage. Proccedings of the 36th International Colloquium Automata, Languages and Programming, ICALP 2009, Rhodes, Greece. LNCS 5555."},{"key":"ref_2","unstructured":"Paluch, K. Faster and simpler approximation of stable matchings. Available online: http:\/\/arxiv.org\/abs\/0911.5660v2."},{"key":"ref_3","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_4","doi-asserted-by":"crossref","unstructured":"Kir\u00e1ly, Z. (2008, January 6). Better and Simpler Approximation Algorithms for the Stable Marriage Problem. Proceedings of the MATCH-UP 2008: Matching Under Preferences\u2014Algorithms and Complexity, Satellite Workshop of ICALP, Reykjav\u00edk, Iceland.","DOI":"10.1007\/978-3-540-87744-8_52"},{"key":"ref_5","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":"Irving","year":"2008","journal-title":"J. Comb. Optim."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Iwama, K., and Miyazaki, S. (2008, January 17). A Survey of the Stable Marriage Problem and Its Variants. Proceedings of the International Conference on Informatics Education and Research for Knowledge-Circulating Society, Kyoto, Japan.","DOI":"10.1109\/ICKS.2008.7"},{"key":"ref_7","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. Algorithms, 3, Article 30.","DOI":"10.1145\/1273340.1273346"},{"key":"ref_8","unstructured":"Iwama, K., Miyazaki, S., and Yamauchi, N. (2007, January 7\u20139). A 1.875-approximation Algorithm for the Stable Marriage Problem. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201907, New Orleans, LA, USA."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/j.tcs.2004.02.045","article-title":"Randomized approximation of the stable marriage problem","volume":"325","author":"Iwama","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Iwama, K., Manlove, D.F., Miyazaki, S., and Morita, Y. (1999, January 11\u201315). Stable Marriage with Incomplete Lists and Ties. Proceedings of the 26th International Colloquium on Automata, Languages and Programming, Prague, Czech. LNCS 1644.","DOI":"10.1007\/3-540-48523-6_41"},{"key":"ref_11","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_12","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_13","unstructured":"Yanagisawa, H. (2007). Approximation Algorithms for Stable Marriage Problems. [Ph.D. Thesis,  Kyoto University]."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Kir\u00e1ly, Z. (2008, January 15\u201317). Better and Simpler Approximation Algorithms for the Stable Marriage Problem. Proceedings of the 16th Annual European Symposium, ESA 2008, Karlsruhe, Germany. LNCS 5193.","DOI":"10.1007\/978-3-540-87744-8_52"},{"key":"ref_15","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_16","unstructured":"Yanagisawa, H. Personal Communication."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Irving, R.W., and Manlove, D.F. (2009). Finding large stable matchings. J. Exp. Algorithmics, 14.","DOI":"10.1145\/1498698.1537595"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Iwama, K., Miyazaki, S., and Yanagisawa, H. (2010, January 6\u20138). A 25\/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties. Proceedings of 18th Annual European Symposium, ESA \u201910, Liverpool, UK. LNCS 6347.","DOI":"10.1007\/978-3-642-15781-3_12"},{"key":"ref_19","unstructured":"Kir\u00e1ly, Z. Approximation of Maximum Stable Marriage, Egres Technical Report TR-2011-03. Available online: http:\/\/www.cs.elte.hu\/egres\/www\/tr-11-03.html."},{"key":"ref_20","unstructured":"Paluch, K. (2011, January 8\u20139). Faster and Simpler Approximation of Stable Matchings. Proceedings of the 9th International Workshop Approximation and Online Algorithms, WAOA 2011, Saarbr\u00fccken, Germany. LNCS 7164."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","article-title":"Storing a sparse table with 0(1) worst case access time","volume":"31","author":"Fredman","year":"1984","journal-title":"J. ACM"},{"key":"ref_22","unstructured":"Gusfield, D., and Irving, R.W. (1989). The Stable Marriage Problem: Structure and Algorithms, MIT Press."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/3\/471\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:48:39Z","timestamp":1760219319000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/3\/471"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8,15]]},"references-count":22,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2013,9]]}},"alternative-id":["a6030471"],"URL":"https:\/\/doi.org\/10.3390\/a6030471","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8,15]]}}}