论文标题
最大稳定匹配与矩形和部分订单
Maximum Stable Matching with Matroids and Partial Orders
论文作者
论文摘要
稳定的婚姻问题（SM）是由著名的大风和沙普利（GS）（GS）著名的接受算法解决的，具有许多自然概括。如果我们允许偏好领域，那么找到最大稳定匹配的问题就会变成NP-HARD，而最著名的近似比为1.5（McDermid 2009，Paluch 2011，Z.Király2012），可以通过在巧妙构建的修改后的实例上运行GS来实现。 SM的另一个优雅概括是Fleiner（2001）引入的矩形核问题，该问题可以在多项式时间内使用抽象的曲霉版本的GS解决。 我们的主要结果是当偏好为间隔订单时，一种简单的1.5-辅助算法，用于Matroid内核问题 - 部分订单的广泛子类，涵盖了许多超出与领带偏好的应用程序。此外，对于双方匹配案例，我们表明算法的输出也1.5-符合相应整数程序的放松的LP-Opt-opt-opt-opt-opt-optimatimation，这表明，间隔顺序案例的完整性差距最多为1.5。为了将其与硬度结果形成鲜明对比，我们表明，如果在偏好中允许任意局部订单，那么即使在两部分匹配案例中，问题也很难在一个因素范围内近似于2，假设唯一的游戏猜想，并且整数差距变为2。
The Stable Marriage problem (SM), solved by the famous deferred acceptance algorithm of Gale and Shapley (GS), has many natural generalizations. If we allow ties in preferences, then the problem of finding a maximum stable matching becomes NP-hard, and the best known approximation ratio is 1.5 (McDermid 2009, Paluch 2011, Z. Király 2012), achievable by running GS on a cleverly constructed modified instance. Another elegant generalization of SM is the matroid kernel problem introduced by Fleiner (2001), which is solvable in polynomial time using an abstract matroidal version of GS. Our main result is a simple 1.5-approximation algorithm for the matroid kernel problem when preferences are given as interval orders -- a broad subclass of partial orders that covers many applications beyond preferences with ties. In addition, for the bipartite matching case, we show that the output of our algorithm also 1.5-approximates the LP-optimum of the relaxation of the corresponding Integer Program, which shows that the integrality gap is at most 1.5 for the interval order case. To contrast this with hardness results, we show that if arbitrary partial orders are allowed in the preferences, then even in the bipartite matching case, the problem becomes hard to approximate within a factor better than 2 assuming the Unique Games Conjecture, and the integrality gap becomes 2.
