A new approach to bipartite stable matching optimization
Tamás Fleiner, András Frank, and Tamás Király
作为先前解决的双方稳定匹配优化问题的通用概括,我们描述了一种基于多项式网络流的算法,用于以最低的总成本计算l不连接的稳定匹配。 方法背后的主要观察是,稳定匹配,作为边缘集合,可以表示为相关定向图的某些切口。 这使我们能够直接使用不连接切的结果来回答有关不连接稳定匹配的问题。 我们还提供了一个结构,在部分有序集合(poset)中表示稳定匹配作为最大尺寸的抗链,这使我们能够将Dilworth,Mirsky,Greene和Kleitman的定理直接应用于稳定的匹配。 这些方法的另一个后果是最小数量的稳定匹配覆盖所有稳定边缘的最小数量公式。
As a common generalization of previously solved optimization problems concerning bipartite stable matchings, we describe a strongly polynomial network flow based algorithm for computing ℓ disjoint stable matchings with minimum total cost. The major observation behind the approach is that stable matchings, as edge sets, can be represented as certain cuts of an associated directed graph. This allows us to use results on disjoint cuts directly to answer questions about disjoint stable matchings. We...
