Quasi-Popular Matchings, Optimality, and Extended Formulations

References

• [1] Abdulkadiroğlu A, Sönmez T (2003) School choice: A mechanism design approach. Amer. Econom. Rev. 93(3):729–747.Crossref, Google Scholar
• [2] Abraham DJ, Irving RW, Kavitha T, Mehlhorn K (2007) Popular matchings. SIAM J. Comput. 37(4):1030–1045.Crossref, Google Scholar
• [3] Baswana S, Chakrabarti PP, Chandran S, Kanoria Y, Patange U (2019) Centralized admissions for engineering colleges in india. INFORMS J. Appl. Analytics 49(5):338–354.Crossref, Google Scholar
• [4] Bazzi A, Fiorini S, Pokutta S, Svensson O (2019) No small linear program approximates vertex cover within a factor 2−ε. Math. Oper. Res. 44(1):147–172.Abstract, Google Scholar
• [5] Bhattacharya S, Hoefer M, Huang C-C, Kavitha T, Wagner L (2015) Maintaining near-popular matchings. Halldórsson MM, Iwama K, Kobayashi N, Speckmann B, eds. Proc. Internat. Colloquium Automata Languages Programming (Springer, Berlin, Heidelberg), 504–515.Google Scholar
• [6] Canadian Resident Matching Service (2019) How the matching algorithm works. Accessed November 15, 2020, https://www.carms.ca/the-match/how-it-works/.Google Scholar
• [7] Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming, vol. 271 (Springer, Berlin).Crossref, Google Scholar
• [8] Cseh Á (2017) Popular matchings. Trends Comput. Soc. Choice 105(3):105–122.Google Scholar
• [9] Cseh Á, Kavitha T (2018) Popular edges and dominant matchings. Math. Programming 172(1–2):209–229.Crossref, Google Scholar
• [10] Cseh Á, Faenza Y, Kavitha T, Powers V (2018) Understanding popular matchings via stable matchings. SIAM J. Discrete Math. Available at https://arxiv.org/abs/1811.06897.Google Scholar
• [11] de Condorcet, Nicolas M (1785) Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. Imprimerie Royale, Paris.Google Scholar
• [12] Faenza Y, Kavitha T (2020) Quasi-popular matchings, optimality, and extended formulations. Chawla S, ed. Proc. 31st Annual ACM-SIAM Sympos. Discrete Algorithms, Salt Lake City (SIAM), 325–344.Google Scholar
• [13] Faenza Y, Kavitha T, Powers V, Zhang X (2019) Popular matchings and limits to tractability. Chan TM, ed. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms, San Diego (SIAM), 2790–2809.Google Scholar
• [14] Feder T (1992) A new fixed point approach for stable networks and stable marriages. J. Comput. System Sci. 45(2):233–284.Crossref, Google Scholar
• [15] Feder T (1994) Network flow and 2-satisfiability. Algorithmica 11(3):291–319.Crossref, Google Scholar
• [16] Gale D, Shapley LS (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69(1):9–15.Crossref, Google Scholar
• [17] Gale D, Sotomayor M (1985) Some remarks on the stable matching problem. Discrete Appl. Math. 11(3):223–232.Crossref, Google Scholar
• [18] Gärdenfors P (1975) Match making: Assignments based on bilateral preferences. Behav. Sci. 20(3):166–173.Crossref, Google Scholar
• [19] Goemans MX (2006) Minimum bounded degree spanning trees. Proc. 47th Annual IEEE Sympos. Foundations Comput. Sci., Berkeley (IEEE), 273–282.Google Scholar
• [20] Göös M, Jain R, Watson T (2018) Extension complexity of independent set polytopes. SIAM J. Comput. 47(1):241–269.Crossref, Google Scholar
• [21] Gupta S, Misra P, Saurabh S, Zehavi M (2019) Popular matching in roommates setting is NP-hard. Chan TM, ed. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms, San Diego (SIAM), 2810–2822.Google Scholar
• [22] Håstad J (2001) Some optimal inapproximability results. J. ACM 48(4):798–859.Crossref, Google Scholar
• [23] Hirakawa M, Yamauchi Y, Kijima S, Yamashita M (2015) On the structure of popular matchings in the stable marriage problem-who can join a popular matching. Third Internat. Workshop Matching Under Preferences, Glasgow.Google Scholar
• [24] Huang C-C, Kavitha T (2013) Near-popular matchings in the roommates problem. SIAM J. Discrete Math. 27(1):43–62.Crossref, Google Scholar
• [25] Huang C-C, Kavitha T (2013) Popular matchings in the stable marriage problem. Inform. Comput. 222:180–194.Crossref, Google Scholar
• [26] Huang C-C, Kavitha T (2021) Popularity, mixed matchings, and self-duality. Math. Oper. Res. 46(2):405–427.Google Scholar
• [27] Irving RW, Leather P, Gusfield D (1987) An efficient algorithm for the “optimal” stable marriage. J. ACM 34(3):532–543.Crossref, Google Scholar
• [28] Kavitha T (2014) A size-popularity tradeoff in the stable marriage problem. SIAM J. Comput. 43(1):52–71.Crossref, Google Scholar
• [29] Kavitha T (2016) Popular half-integral matchings. Chatzigiannakis I, Mitzenmacher M, Rabani Y, Sangiorgi D, eds. Proc. 43rd Internat. Colloquium Automata Languages Programming, Rome, 22(1–22):13.Google Scholar
• [30] Kavitha T, Mestre J, Nasre M (2011) Popular mixed matchings. Theoret. Comput. Sci. 412(24):2679–2690.Crossref, Google Scholar
• [31] Makarychev K, Makarychev Y, Sviridenko M, Ward J (2015) A bi-criteria approximation algorithm for k means. Preprint, submitted July 15, https://arxiv.org/abs/1507.04227.Google Scholar
• [32] McCutchen RM (2008) The least-unpopularity-factor and least-unpopularity-margin criteria for matching problems with one-sided preferences. Laber ES, Claudson B, Loana TN, Luerbio F, eds. Proc. Latin Amer. Sympos. Theoret. Informatics, Buzios (Springer), 593–604.Google Scholar
• [33] Merrill S, Grofman B (1999) A Unified Theory of Voting: Directional and Proximity Spatial Models (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [34] National Resident Matching Program (2019) The MATCH annual report. Accessed November 15, 2020, https://annualreport.nrmp.org/.Google Scholar
• [35] Rothblum UG (1992) Characterization of stable matchings as extreme points of a polytope. Math. Programming 54(1–3):57–67.Crossref, Google Scholar
• [36] Rothvoß T (2017) The matching polytope has exponential extension complexity. J. ACM 64(6):1–19.Crossref, Google Scholar
• [37] Ruangwises S, Itoh T (2020) Unpopularity factor in the marriage and roommates problems. Theory Comput. Systems 65(3):1–14.Google Scholar
• [38] Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency, vol. 24 (Springer, Berlin-Heidelberg).Google Scholar
• [39] Singh M, Lau LC (2015) Approximating minimum bounded degree spanning trees to within one of optimal. J. ACM 62(1):1–19.Crossref, Google Scholar
• [40] Teo C-P, Sethuraman J (1998) The geometry of fractional stable matchings and its applications. Math. Oper. Res. 23(4):874–891.Link, Google Scholar
• [41] Vande Vate JH (1989) Linear programming brings marital bliss. Oper. Res. Lett. 8(3):147–153.Crossref, Google Scholar