Linear Time Local Approximation Algorithm for Maximum Stable Marriage
Linear Time Local Approximation Algorithm for Maximum Stable Marriage
复制标题
最大稳定婚姻的线性时间局部逼近算法
作者：
Z. Király
我们考虑不完全偏好列表下的双边市场，其目标是找到最大规模的稳定匹配。该问题是 APX 难题，McDermid [1] 给出了 3/2 近似值。该算法具有非线性运行时间，更重要的是需要所有偏好列表的全局知识。我们使用 Paluch [2] 的一些思想，提出了一种非常自然、经济合理、具有相同比率的局部线性时间算法。在这个算法中，每个人仅使用自己的列表以及从这些列表的成员那里询问的一些信息来做出决策（就像著名的 Gale 和 Shapley 算法一样）。还讨论了对医院/居民问题的一些后果。
We consider a two-sided market under incomplete preference lists with ties, where the goal is to find a maximum size stable matching. The problem is APX-hard, and a 3/2-approximation was given by McDermid [1]. This algorithm has a non-linear running time, and, more importantly needs global knowledge of all preference lists. We present a very natural, economically reasonable, local, linear time algorithm with the same ratio, using some ideas of Paluch [2]. In this algorithm every person make decisions using only their own list, and some information asked from members of these lists (as in the case of the famous algorithm of Gale and Shapley). Some consequences to the Hospitals/Residents problem are also discussed.