Quasi-popular matchings, optimality, and extended formulations
From MaRDI portal
Publication:5076707
DOI10.1287/MOOR.2021.1139zbMATH Open1489.05116arXiv1904.05974OpenAlexW3207901828MaRDI QIDQ5076707FDOQ5076707
Authors: Yuri Faenza, Telikepalli Kavitha 
Publication date: 17 May 2022
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Abstract: Let G = ((A,B),E) be an instance of the stable marriage problem where 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 are a well-studied generalization of stable matchings, introduced with the goal of enlarging the set of admissible solutions, while maintaining a certain level of fairness. Every stable matching is a min-size popular matching. Unfortunately, when there are edge costs, it is NP-hard to find a popular matching of minimum cost -- even worse, the min-cost popular matching problem is hard to approximate up to any factor. 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 bi-criteria algorithms that find in polynomial time a near-popular or 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. This version of the paper goes beyond the conference version [12] in the following two points: (i) the algorithm for finding a quasi-popular matching of cost at most that of a min-cost popular fractional matching is new; (ii) the proofs from Section 6.1 and Section 7.3 are now self-contained (the conference version used constructions from [10] to show these lower bounds).
Full work available at URL: https://arxiv.org/abs/1904.05974
Recommendations
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)
Cites Work
- Some remarks on the stable matching problem
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Some optimal inapproximability results
- College Admissions and the Stability of Marriage
- The geometry of fractional stable matchings and its applications
- Linear programming brings marital bliss
- Characterization of stable matchings as extreme points of a polytope
- Popular Matchings
- Popular matchings and limits to tractability
- Network flow and 2-satisfiability
- Approximating minimum bounded degree spanning trees to within one of optimal
- Integer Programming
- Popular mixed matchings
- The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences
- A new fixed point approach for stable networks and stable marriages
- Extension complexity of independent set polytopes
- Popular matchings in the stable marriage problem
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- A Size-Popularity Tradeoff in the Stable Marriage Problem
- Popular Half-Integral Matchings.
- Quasi-popular Matchings, Optimality, and Extended Formulations
- Maintaining Near-Popular Matchings
- Near-popular matchings in the roommates problem
- Understanding popular matchings via stable matchings
- Popularity, Mixed Matchings, and Self-Duality
Cited In (5)
This page was built for publication: Quasi-popular matchings, optimality, and extended formulations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5076707)
