{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T06:20:55Z","timestamp":1778739655952,"version":"3.51.4"},"reference-count":17,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2014,4,4]],"date-time":"2014-04-04T00:00:00Z","timestamp":1396569600000},"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 give a    3 2    -approximation algorithm for finding stable matchings that runs in O(m) time. The previous most well-known algorithm, by McDermid, has the same approximation ratio but runs in O(n3\/2m) time, where n denotes the number of people andm is the total length of the preference lists in a given instance. In addition, the algorithm and the analysis are much simpler. We also give the extension of the algorithm for computing stable many-to-many matchings.<\/jats:p>","DOI":"10.3390\/a7020189","type":"journal-article","created":{"date-parts":[[2014,4,4]],"date-time":"2014-04-04T11:11:12Z","timestamp":1396609872000},"page":"189-202","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["Faster and Simpler Approximation of Stable Matchings"],"prefix":"10.3390","volume":"7","author":[{"given":"Katarzyna","family":"Paluch","sequence":"first","affiliation":[{"name":"Institute of Computer Science, University of Wroc\u0142aw, Joliot-Curie 15, 50\u2013383 Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,4,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1954","DOI":"10.1257\/aer.99.5.1954","article-title":"Strategy-proofness vs. Efficiency in matching with indifferences: Redesigning the NYC high school match","volume":"99","author":"Abdulkadiroglu","year":"2009","journal-title":"Am. Econ. Rev."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1257\/aer.98.3.669","article-title":"What\u2019s the Matter with Tie-Breaking? Improving Efficiency in School Choice","volume":"98","author":"Erdil","year":"2008","journal-title":"Am. Econ. Rev."},{"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","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. Comp. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/1273340.1273346","article-title":"Improved approximation results for the stable marriage problem","volume":"3","author":"Iwama","year":"2007","journal-title":"ACM Trans. Algorithms"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Irving, R.W., and Manlove, D. (2009). Finding large stable matchings. ACM J. Exp. Algorithmics, 14, article 2.","DOI":"10.1145\/1498698.1537595"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2380","DOI":"10.1093\/ietisy\/e89-d.8.2380","article-title":"A (\n\t\t\t\t\t\t\t        \n\t\t\t\t\t\t\t          \n\t\t\t\t\t\t\t            \n\t\t\t\t\t\t\t              2\n\t\t\t\t\t\t\t\t\t\t  \u2212\n\t\t\t\t\t\t\t\t\t\t  c\n\t\t\t\t\t\t\t\t\t\t  \n\t\t\t\t\t\t\t                  \n\t\t\t\t\t\t\t                    log\n\t\t\t\t\t\t\t                      n\n\t\t\t\t\t\t\t                  \n\t\t\t\t\t\t\t\t\t\t\t  n\n\t\t\t\t\t\t\t                \n\t\t\t\t\t\t\t            \n\t\t\t\t\t\t\t          \n\t\t\t\t\t\t\t        \n\t\t\t\t\t\t\t      )-approximation algorithm for the stable marriage problem","volume":"89-D","author":"Iwama","year":"2006","journal-title":"IEICE Trans."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/s00453-007-9101-y","article-title":"A (\n\t\t\t\t\t\t\t\t        \n\t\t\t\t\t\t\t\t          \n\t\t\t\t\t\t\t\t            \n\t\t\t\t\t\t\t\t              2\n\t\t\t\t\t\t\t\t\t\t\t  \u2212\n\t\t\t\t\t\t\t\t\t\t\t  c\n\t\t\t\t\t\t\t\t\t\t\t  \n\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\t\t\t  n\n\t\t\t\t\t\t\t\t\t\t\t\t  \n\t\t\t\t\t\t\t\t                \n\t\t\t\t\t\t\t\t            \n\t\t\t\t\t\t\t\t          \n\t\t\t\t\t\t\t\t        \n\t\t\t\t\t\t\t\t      )-approximation algorithm for the stable marriage problem","volume":"51","author":"Iwama","year":"2008","journal-title":"Algorithmica"},{"key":"ref_9","unstructured":"Bansal, N., Pruhs, K., and Stein, C. (2007, January January). A 1:875-approximation algorithm for the stable marriage problem. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, New Orleans."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/978-3-642-15781-3_12","article-title":"A 25\/17-Approximation algorithm for the stable marriage problem with one-sided ties","volume":"6347","author":"Iwama","year":"2010","journal-title":"Lect. Notes Comp. Sci."},{"key":"ref_11","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_12","unstructured":"Kir\u00e1ly, Z. (2011). Approximation of Maximum Stable Marriage, The Egerv\u00e1ry Research Group. Technical Report TR-2011-0."},{"key":"ref_13","unstructured":"Lov\u00e1sz, L., and Plummer, M.D. (,  1986). Matching Theory. Annals of Discrete Mathematics 29, North-Holland, Amsterdam."},{"key":"ref_14","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_15","doi-asserted-by":"crossref","unstructured":"Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., and Thomas, W. (,  2009). A 3\/2-approximation algorithm for general stable marriage. Proceedings of the Automata, Languages and Programming, 36th International Colloquium, ICALP, Rhodes, Greece.","DOI":"10.1007\/978-3-642-02927-1"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Solis-Oba, R., and Persiano, G. (,  2011). Faster and simpler approximation of stable matchings. Proceedings of the WAOA \u201911: 9th Workshop on Approximation and Online Algorithms, Saarbruecken, Germany.","DOI":"10.1007\/978-3-642-29116-6"},{"key":"ref_17","unstructured":"Yanagisawa, H. (2007). Approximation Algorithms for Stable Marriage Problems. [Ph.D. Thesis, Kyoto University]."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/2\/189\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:09:56Z","timestamp":1760216996000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/2\/189"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4,4]]},"references-count":17,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2014,6]]}},"alternative-id":["a7020189"],"URL":"https:\/\/doi.org\/10.3390\/a7020189","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4,4]]}}}