论文标题
晶格线性谓语算法，用于稳定稳定婚姻问题
Lattice Linear Predicate Algorithms for the Constrained Stable Marriage Problem with Ties
论文作者
论文摘要
我们将晶格线性谓词检测技术应用于稳定匹配问题的各种变体的平行和分布式算法。这些问题是：（a）稳定的婚姻问题（b）在存在关系的情况下，超级稳定的婚姻问题，以及（c）在存在领带的情况下，强烈稳定的婚姻。所有这些问题均使用晶格线性谓词（LLP）算法来解决。受约束的稳定婚姻问题是在存在晶格线性约束的情况下找到稳定婚姻的一种版本，例如``彼得的遗憾都比Paul的遗憾少。我们的算法完全异步。我们针对稳定婚姻问题的算法也与没有同步的算法也平行。
We apply Lattice-Linear Predicate Detection Technique to derive parallel and distributed algorithms for various variants of the stable matching problem. These problems are: (a) the constrained stable marriage problem (b) the super stable marriage problem in presence of ties, and (c) the strongly stable marriage in presence of ties. All these problems are solved using the Lattice-Linear Predicate (LLP) algorithm showing its generality. The constrained stable marriage problem is a version of finding the stable marriage in presence of lattice-linear constraints such as ``Peter's regret is less than that of Paul.'' For the constrained stable marriage problem, we present a distributed algorithm that takes $O(n^2)$ messages each of size $O(\log n)$ where $n$ is the number of men in the problem. Our algorithm is completely asynchronous. Our algorithms for the stable marriage problem with ties are also parallel with no synchronization.
