A Simple 1.5-Approximation Algorithm for a Wide Range of Maximum-Size Stable Matching Problems

References

• [1] Askalidis G, Immorlica N, Kwanashie A, Manlove DF, Pountourakis E (2013) Socially stable matchings in the hospitals/residents problem. Dehne F, Solis-Oba R, Sack JR, eds. Algorithms Data Structures. WADS 2013, Lecture Notes in Computer Science, vol. 8037 (Springer, Berlin, Heidelberg), 85–96.Google Scholar
• [2] Cechlárová K, Fleiner T (2009) Stable roommates with free edges. Technical Report 2009-01, Egerváry Research Group on Combinatorial Optimization, Budapest.Google Scholar
• [3] Chen J, Skowron P, Sorge M (2021) Matchings under preferences: Strength of stability and tradeoffs. ACM Trans. Econom. Comput. 9(4):1–55.Crossref, Google Scholar
• [4] Csáji G, Király T, Yokoi Y (2023) Approximation algorithms for matroidal and cardinal generalizations of stable matching. Kavitha T, Mehlhorn K, eds. Sympos. Simplicity Algorithms (SOSA) (SIAM, Philadelphia), 103–113.Google Scholar
• [5] Cseh Á, Heeger K (2020) The stable marriage problem with ties and restricted edges. Discrete Optim. 36:100571.Crossref, Google Scholar
• [6] Dudycz S, Manurangsi P, Marcinkowski J (2022) Tight inapproximability of minimum maximal matching on bipartite graphs and related problems. Koenemann J, Peis B, eds. Approximation Online Algorithms. WAOA 2021, Lecture Notes in Computer Science, vol. 12982 (Springer, Cham, Switzerland), 48–64.Google Scholar
• [7] Fleiner T (2001) A matroid generalization of the stable matching polytope. Aardal K, Gerards B, eds. Integer Programming Combin. Optim. IPCO 2001, Lecture Notes in Computer Science, vol. 2081 (Springer, Berlin, Heidelberg), 105–114.Google Scholar
• [8] Gale D, Shapley LS (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69(1):9–15.Crossref, Google Scholar
• [9] Halldórsson M, Iwama K, Miyazaki S, Morita Y (2002) Inapproximability results on stable marriage problems. Rajsbaum S, ed. LATIN 2002: Theoret. Inform., Lecture Notes in Computer Science, vol. 2286 (Springer, Berlin, Heidelberg), 554–568.Google Scholar
• [10] Halldórsson MM, Iwama K, Miyazaki S, Yanagisawa H (2003) Improved approximation of the stable marriage problem. Di Battista G, Zwick U, eds. Algorithms - ESA 2003, Lecture Notes in Computer Science, vol. 2832 (Springer, Berlin, Heidelberg), 266–277.Google Scholar
• [11] Iwama K, Miyazaki S, Yamauchi N (2007) A 1.875-approximation algorithm for the stable marriage problem. Proc. 18th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA 2007) (SIAM, Philadelphia), 288–297.Google Scholar
• [12] Iwama K, Miyazaki S, Yamauchi N (2008) A (2−c1n)-approximation algorithm for the stable marriage problem. Algorithmica 51(3):342–356.Crossref, Google Scholar
• [13] Iwama K, Manlove D, Miyazaki S, Morita Y (1999) Stable marriage with incomplete lists and ties. Wiedermann J, van Emde Boas P, Nielsen M, eds. Automata Languages Programming, Lecture Notes in Computer Science, vol. 1644 (Springer, Berlin, Heidelberg), 443–452.Google Scholar
• [14] Király Z (2011) Better and simpler approximation algorithms for the stable marriage problem. Algorithmica 60(1):3–20.Crossref, Google Scholar
• [15] Király Z (2013) Linear time local approximation algorithm for maximum stable marriage. Proc. 2nd Internat. Workshop Matching under Preferences (MATCH-UP 2012) (Budapest, Hungary), 99.Google Scholar
• [16] Király Z (2013) Linear time local approximation algorithm for maximum stable marriage. Algorithms 6(3):471–484.Crossref, Google Scholar
• [17] Krishnaa P, Limaye G, Nasre M, Nimbhorkar P (2023) Envy-freeness and relaxed stability: Hardness and approximation algorithms. J. Combin. Optim. 45(1):41.Crossref, Google Scholar
• [18] Manlove D (2013) Algorithmics of Matching Under Preferences, vol. 2 (World Scientific Publishing, Singapore).Google Scholar
• [19] McDermid E (2009) A 3/2-approximation algorithm for general stable marriage. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas S, Thomas W, eds. Automata Languages Programming. ICALP 2009, Lecture Notes in Computer Science, vol. 5555 (Springer, Berlin, Heidelberg), 689–700.Google Scholar
• [20] Nasre M, Rawat A (2017) Popularity in the generalized hospital residents setting. Weil P, ed. Comput. Sci. – Theory Appl. CSR 2017, Lecture Notes in Computer Science, vol. 10304 (Springer, Cham, Switzerland), 245–259.Google Scholar
• [21] Nasre M, Nimbhorkar P, Ranjan K (2023) Critical relaxed stable matchings with two-sided ties. Preprint, submitted March 22, https://arxiv.org/abs/2303.12325.Google Scholar
• [22] Nasre M, Nimbhorkar P, Ranjan K (2023) Critical relaxed stable matchings with two-sided ties. Paulusma D, Ries B, eds. Graph-Theoret. Concepts Comput. Sci. WG 2023, Lecture Notes in Computer Science, vol. 14093 (Springer, Cham, Switzerland), 447–461.Google Scholar
• [23] Paluch K (2011) Faster and simpler approximation of stable matchings. Solis-Oba R, Persiano G, eds. Approximation Online Algorithms. WAOA 2011, Lecture Notes in Computer Science, vol. 7164 (Springer, Berlin, Heidelberg), 176–187.Google Scholar
• [24] Paluch K (2014) Faster and simpler approximation of stable matchings. Algorithms 7(2):189–202.Crossref, Google Scholar
• [25] Silvia Pini M, Rossi F, Venable KB, Walsh T (2013) Stability, optimality and manipulation in matching problems with weighted preferences. Algorithms 6(4):782–804.Crossref, Google Scholar
• [26] Yanagisawa H (2007) Approximation algorithms for stable marriage problems. Unpublished PhD thesis, Kyoto University Graduate School of Informatics, Kyoto, Japan.Google Scholar
• [27] Yokoi Y (2021) An approximation algorithm for maximum stable matching with ties and constraints. 32nd Internat. Sympos. Algorithms Comput. (ISAAC 2021) (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 71:1–71:16.Google Scholar