论文标题
与有限不稳定性的最大通俗性比赛
Maximum-utility popular matchings with bounded instability
论文作者
论文摘要
在顶点比邻居偏好的图表中，如果在比赛之间的顶点投票时，它不会因其他任何匹配而失去其他任何匹配的匹配选举，则称为受欢迎。流行的比赛可以看作是稳定匹配和最大尺寸匹配之间的中间类别。在本文中，我们旨在最大化受欢迎的匹配功能，但仅承认几个封锁边缘。 对于已经找到与一个受欢迎的匹配的一般图表，最多是一个封锁边缘是NP完整的。对于双方实例，我们研究了找到最大的通用匹配的问题，该匹配与使用多元方法的限制（或更一般的成本）限制了（或更一般的成本）。我们显示了严格限制实例的经典和参数化硬度结果。相比之下，我们设计了一种算法，用于一侧偏好允许主列表的实例，并证明该算法是最佳的。
In a graph where vertices have preferences over their neighbors, a matching is called popular if it does not lose a head-to-head election against any other matching when the vertices vote between the matchings. Popular matchings can be seen as an intermediate category between stable matchings and maximum-size matchings. In this paper, we aim to maximize the utility of a matching that is popular but admits only a few blocking edges. For general graphs already finding a popular matching with at most one blocking edge is NP-complete. For bipartite instances, we study the problem of finding a maximum-utility popular matching with a bound on the number (or more generally, the cost) of blocking edges applying a multivariate approach. We show classical and parameterized hardness results for severely restricted instances. By contrast, we design an algorithm for instances where preferences on one side admit a master list, and show that this algorithm is optimal.
