Faster and Simpler Approximation of Stable Matchings
Faster and Simpler Approximation of Stable Matchings
复制标题
更快、更简单地近似稳定匹配
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Katarzyna E. Paluch
中科院分区：
文献类型：
--
作者：
Katarzyna E. Paluch
我们给出了一个 3/2 近似算法，用于在 O(m) 时间内运行的稳定匹配。 McDermid 之前最著名的算法具有相同的近似率，但运行时间为 O(n3/2m)，其中 n 表示人数，m 是给定实例中偏好列表的总长度。而且算法和分析也简单得多。我们还给出了计算稳定多对多匹配的算法的扩展。
We give a 3/2-approximation algorithm for stable matchings that runs in O(m) time. The previously best known algorithm by McDermid has the same approximation ratio but runs in O(n3/2m) time, where n denotes the number of people and m is the total length of the preference lists in a given instance. Also the algorithm and the analysis are much simpler. We also give the extension of the algorithm for computing stable many-to-many matchings.