Quasi-Popular Matchings, Optimality, and Extended Formulations

Yuri Faenza () and Telikepalli Kavitha ()
Additional contact information
Yuri Faenza: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Telikepalli Kavitha: School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai 400005, India

Mathematics of Operations Research, 2022, vol. 47, issue 1, 427-457

Abstract: 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.

Keywords: Primary: 05C70; secondary: 91B68; 90C57; popular matching; extended formulation; quasi-popularity; dominant matching (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1139 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:1:p:427-457

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().