Classified stable matching
Classified stable matching
复制标题
分类稳定匹配
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Chien
中科院分区：
文献类型：
--
作者：
Chien
我们介绍了分类稳定匹配问题，一个问题的动机是学术招聘。假设一些机构正在从一批申请者中招聘教员。机构和申请人都有优先权。研究所根据申请人的研究领域（或任何其他标准）对申请人进行分类，并且对于每个类别，它为该类别中的申请人数量设定了下限和上限。我们的目标是找到一个稳定的匹配，从没有一组参与者有理由偏离。此外，匹配应该尊重类的上/下界。本文的第一部分研究了分类属于固定“序类型”集合的分类稳定匹配问题。“我们证明，如果集合完全由向下森林组成，则存在多项式时间算法;否则，决定稳定匹配的存在是NP完全的。
在第二部分中，我们使用多面体的方法来研究这个问题。假设所有的分类都是层状族，并且没有下界。我们提出了一组线性不等式来描述稳定的匹配多面体，并证明了它是完整的。这个完整性的结果使我们能够找到最佳的稳定匹配在多项式时间内使用椭球算法，此外，它给出了一个描述的稳定匹配多面体的多对多（未分类）稳定匹配问题，从而回答了一个公开的问题Sethuraman，Teo和钱。
We introduce the classified stable matching problem, a problem motivated by academic hiring. Suppose that a number of institutes are hiring faculty members from a pool of applicants. Both institutes and applicants have preferences over the other side. An institute classifies the applicants based on their research areas (or any other criterion), and, for each class, it sets a lower bound and an upper bound on the number of applicants it would hire in that class. The objective is to find a stable matching from which no group of participants has reason to deviate. Moreover, the matching should respect the upper/lower bounds of the classes. In the first part of the paper, we study classified stable matching problems whose classifications belong to a fixed set of "order types." We show that if the set consists entirely of downward forests, there is a polynomial-time algorithm; otherwise, it is NP-complete to decide the existence of a stable matching.
In the second part, we investigate the problem using a polyhedral approach. Suppose that all classifications are laminar families and there is no lower bound. We propose a set of linear inequalities to describe stable matching polytope and prove that it is integral. This integrality result allows us to find optimal stable matchings in polynomial time using Ellipsoid algorithm; furthermore, it gives a description of the stable matching polytope for the many-to-many (unclassified) stable matching problem, thereby answering an open question posed by Sethuraman, Teo and Qian.