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

Question

假设我有两组:(n_1,n_2,...)和(m_1,m_2,...)和匹配函数匹配(n,m),它返回0到1之间的值.我想找到两组之间的映射,以满足以下约束:

• 每个元素在相反的集合中必须至多有1个匹配的元素.
• 不匹配的元素将与成本1的虚拟元素配对
• 应用于所有元素时匹配函数的总和是最大的
• 我无法正式表达这一点,但是如果你按照原始顺序排列每个彼此平行的组并在匹配的元素之间画一条线,那么任何一条线都不会交叉.Ex [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 _a和m ₁,...,m _b上的最佳匹配的值.我们已经复发了

M(0,b)= -b
M(a,0)= -a
M(a,b)= max {M(a-1,b-1)+ match(a,b),M(a-1) ,b) - 1,M(a,b - 1) - 1}.

通过追溯argmax,您可以从其值中恢复最佳解决方案.

如果匹配明显少于大于-1的二次数条目,则存在一种算法,其在有用条目的数量(Khoo和Cong,用于MCM设计的快速多层通用区域路由器)中以时间线性运行.