Polyhedral Aspects of Stable Marriage

• 成果类型: Article
• 署名作者: Eirinakis, Pavlos; Magos, Dimitrios; Mourtos, Ioannis; Miliotis, Panayiotis
• 署名单位: Athens University of Economics & Business; University of West Attica
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2013.0616
• 发表日期: 2014
• 页码: 656-671
• 关键词: matchings; polytope

摘要

In the setting of the stable matching (SM) problem, it has been observed that some of the man-woman pairs cannot be removed although they participate in no stable matching, since such a removal would alter the set of solutions. These pairs are yet to be identified. Likewise (and despite the sizeable literature), some of the fundamental characteristics of the SM polytope (e.g., its dimension, its facets, etc.) have not been established. In the current work, we show that these two seemingly distant open issues are closely related. More specifically, we identify the pairs with the above-mentioned property and present a polynomial algorithm for producing a set of minimal preference lists. We utilize this result in the context of two different representations of the SM structure (rotation-poset graph and algebraic formulation) and derive the dimension of the SM polytope to obtain all alternative minimal linear descriptions.