最大加权二分配匹配约束：每个图的排序被保留

Question

假设我有两个集合：（n_1，n_2，...）和（m_1，m_2，...）和一个匹配函数match（n， m）返回一个从0到1的值。我想要找到两组之间的映射关系，以满足以下约束条件：

• 每个元素在对立集合中必须至多有一个匹配元素。
• 无与伦比的元素将与虚设的元素按成本进行配对1
• 当应用于所有元素的匹配函数的总和是最大
• 我无法正式表达这一点，但如果你一字排开各组并行彼此之间的原始顺序，并在匹配的元素之间划出一条线，这些线都不会交叉。 E.x. [n_1 < - > m_2，n_2 < - > m_3]是一个有效的映射，但[n_1 < - > m_2，n_2 < - > m_1]不是。

（我认为前三个标准赋权的匹配约束，但我指定他们的情况下，我误解了赋权的匹配）

这是相对简单的，在指数时间穷举搜索做（关于集合的大小），但我希望有一个多项式时间（理想情况下是O（（| n | * | m |）^ 3）或更好）解。

我已经在“分配问题”/“加权二分配匹配”上搜索了相当数量的数据，并且看到了具有不同约束条件的变体，但没有找到匹配的数据或者我可以减少到一个排序约束。你有什么想法可以解决这个问题吗？或者可能是一个粗略的证明，表明它在多项式时间内是不可解的（对于我的目的而言，减少NP-complete也是可行的）？

Answer 1

此问题已在“最大重量非交叉匹配”的名称下进行了研究。有一个简单的二次时间动态程序。设M（A，B）是n个最佳匹配的值，...，N _一个且m ，...，M _b。我们有复发

M（0，B）= -b
M（A，0）= -a
M（A，B）=最大{M（一 - 1，B - 1 ）+匹配（a，b），M（a-1，b）-1，M（a，b-1）-1}。

通过追溯argmaxes，您可以从它的值中恢复最优解。

如果匹配的次数大于-1的二次数大大少于两次，则有一个算法在时间线性方向上运行有用的条目数（Khoo and Cong, A Fast Multilayer General Area Router for MCM Designs）。