最大加權二分配匹配約束：每個圖的排序被保留

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）。