论文标题
近似稳定的匹配与有界的关系
Approximating Stable Matchings with Ties of Bounded Size
论文作者
论文摘要
寻找稳定的匹配是算法游戏理论中的核心问题之一。如果允许参与者有联系和不完整的偏好，则已知计算最大基数的稳定匹配将是NP-HARD。在本文中，我们提出了$（3L-2）/（2L-1）$ - 稳定匹配问题的近似算法，最多$ L $和不完整的列表。我们的结果与相关的LP公式的整数差距上的已知下限匹配。
Finding a stable matching is one of the central problems in algorithmic game theory. If participants are allowed to have ties and incomplete preferences, computing a stable matching of maximum cardinality is known to be NP-hard. In this paper we present a $(3L-2)/(2L-1)$-approximation algorithm for the stable matching problem with ties of size at most $L$ and incomplete lists. Our result matches the known lower bound on the integrality gap for the associated LP formulation.
