Quasi-Popular Matchings, Optimality, and Extended Formulations
From MaRDI portal
Publication:5076707
DOI10.1287/moor.2021.1139zbMath1489.05116arXiv1904.05974OpenAlexW3207901828MaRDI QIDQ5076707
Yuri Faenza, Telikepalli Kavitha
Publication date: 17 May 2022
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.05974
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)
Related Items (1)
Cites Work
- Popular mixed matchings
- Some remarks on the stable matching problem
- Linear programming brings marital bliss
- Characterization of stable matchings as extreme points of a polytope
- A new fixed point approach for stable networks and stable marriages
- Network flow and 2-satisfiability
- Popular edges and dominant matchings
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Popular matchings in the stable marriage problem
- The Geometry of Fractional Stable Matchings and Its Applications
- Integer Programming
- Maintaining Near-Popular Matchings
- Popular Matchings
- Popular Half-Integral Matchings.
- Extension Complexity of Independent Set Polytopes
- The Matching Polytope has Exponential Extension Complexity
- Popularity, Mixed Matchings, and Self-Duality
- Understanding Popular Matchings via Stable Matchings
- Popular Matching in Roommates Setting Is NP-hard
- Quasi-popular Matchings, Optimality, and Extended Formulations
- No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ
- Popular Matchings and Limits to Tractability
- Near-Popular Matchings in the Roommates Problem
- A Size-Popularity Tradeoff in the Stable Marriage Problem
- Some optimal inapproximability results
- The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences
- Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
- College Admissions and the Stability of Marriage
This page was built for publication: Quasi-Popular Matchings, Optimality, and Extended Formulations
