Quasi-Popular Matchings, Optimality, and Extended Formulations

• 成果类型: Article
• 署名作者: Faenza, Yuri; Kavitha, Telikepalli
• 署名单位: Columbia University; Tata Institute of Fundamental Research (TIFR)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1139
• 发表日期: 2022
• 页码: 427-457
• 关键词: Stable matchings; admissions

摘要

Let G be an instance of the stable marriage problem in which every vertex ranks its neighbors in a strict order of preference. A matching M in G is popular if M does not lose a head-to-head election against any matching. Popular matchings generalize stable matchings. Unfortunately, when there are edge costs, to find or even approximate up to any factor a popular matching of minimum cost is NP-hard. Let opt be the cost of a min-cost popular matching. Our goal is to efficiently compute a matching of cost at most opt by paying the price of mildly relaxing popularity. Our main positive results are two bicriteria algorithms that find in polynomial time a quasi-popular matching of cost at most opt. Moreover, one of the algorithms finds a quasi-popular matching of cost at most that of a min-cost popular fractional matching, which could be much smaller than opt. Key to the other algorithm is a polynomial-size extended formulation for an integral polytope sandwiched between the popular and quasi-popular matching polytopes. We complement these results by showing that it is NP-hard to find a quasi-popular matching of minimum cost and that both the popular and quasi-popular matching polytopes have near-exponential extension complexity.