Pareto optimality in the Roommates Problem
Pareto optimality in the Roommates Problem
复制标题
室友问题中的帕累托最优
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
D. Manlove
中科院分区：
文献类型：
--
作者：
David J. Abraham;D. Manlove
我们认为帕累托最优匹配是一种处理不允许稳定匹配的稳定室友问题（SR）实例的方法。给定SR的实例I，我们证明了寻找最大帕累托最优匹配的问题在O（√nα(m, n)m log n）时间内可解决，其中n是智能体的数量，m是I中偏好列表的总长度。相反，我们证明了寻找最小帕累托最优匹配的问题是np困难的，尽管在2内近似。我们还证明了寻找具有最少阻塞对数量的Pareto最优匹配的问题是np困难的。然而，对于一个固定的整数K，我们给出了一个多项式时间算法，该算法构造了一个最多K个块对的Pareto最优匹配，或者报告不存在这样的匹配。
We consider Pareto optimal matchings as a means of coping with instances of the Stable Roommates problem (SR) that do not admit a stable matching. Given an instance I of SR, we show that the problem of finding a maximum Pareto optimal matching is solvable in O( √ nα(m, n)m log n) time, where n is the number of agents and m is the total length of the preference lists in I. By contrast we prove that the problem of finding a minimum Pareto optimal matching is NP-hard, though approximable within 2. We also show that the problem of finding a Pareto optimal matching with the fewest number of blocking pairs is NP-hard. However, for a fixed integer K, we give a polynomial-time algorithm that constructs a Pareto optimal matching with at most K blocking pairs, or reports that no such matching exists.