论文标题
适应稳定的匹配到强迫和禁止对
Adapting Stable Matchings to Forced and Forbidden Pairs
论文作者
论文摘要
我们介绍了适应强迫和禁止对的稳定匹配的问题。具体而言，鉴于稳定的匹配$ m_1 $，一套$ q $ of强制对，以及一套$ p $ purebidden forbidden对，我们希望找到一个稳定的匹配，其中包括所有对$ q $，no p $ p $ the pair the pair the pair，to p $ the top p $，并且尽可能接近$ m_1 $。我们在四个经典稳定的匹配环境中研究了这个问题：稳定的室友（带有联系）和稳定的婚姻（带有领带）。作为我们的主要贡献，我们采用稳定室友的旋转理论来开发一种多项式时算法，以适应稳定的室友匹配对强制对。与此相反，我们表明禁止对的问题是NP-HARD。但是，对于只有强制对的情况，我们的多项式时间算法就可以将其扩展到相对于禁止对的固定参数可拖动算法。此外，我们还研究偏好包含关系的设置。在这里，根据所选的稳定性标准，我们表明我们的算法结果可以扩展，或者以前可拖延的问题变得棘手。
We introduce the problem of adapting a stable matching to forced and forbidden pairs. Specifically, given a stable matching $M_1$, a set $Q$ of forced pairs, and a set $P$ of forbidden pairs, we want to find a stable matching that includes all pairs from $Q$, no pair from $P$, and that is as close as possible to $M_1$. We study this problem in four classical stable matching settings: Stable Roommates (with Ties) and Stable Marriage (with Ties). As our main contribution, we employ the theory of rotations for Stable Roommates to develop a polynomial-time algorithm for adapting Stable Roommates matchings to forced pairs. In contrast to this, we show that the same problem for forbidden pairs is NP-hard. However, our polynomial-time algorithm for the case of only forced pairs can be extended to a fixed-parameter tractable algorithm with respect to the number of forbidden pairs when both forced and forbidden pairs are present. Moreover, we also study the setting where preferences contain ties. Here, depending on the chosen stability criterion, we show either that our algorithmic results can be extended or that formerly tractable problems become intractable.
