Maximum weighted bipartite correspondence, restriction: the ordering of each graph is preserved

Question

Let's say I have two sets: (n_1, n_2, ...) and (m_1, m_2, ...) and a matching match (n, m) function that returns a value from 0 to 1. I want to find a match between two sets so that the following restrictions are met:

• Each element must have at most 1 matched element in the opposite set.
• Unmatched items will be connected to the dummy item at a cost of 1
• The sum of the matching function when applied to all elements as much as possible
• I am having trouble expressing this formally, but if you built each set parallel to each other with their original order and drew a line between the matched elements, none of the lines would cross. Ex [n_1 ↔ m_2, n_2 ↔ m_3] is a valid map, but [n_1 ↔ m_2, n_2 ↔ m_1] is not.

(I believe the first three are standard weighted bipartisan ties, but I indicated them if I misunderstood the weighted bipartite correspondence)

This is relatively straightforward to do with an exhaustive search in exponential time (by the size of the sets), but I hope for polynomial time (ideally O ((| n | * | m |) ^ 3) or better).

I searched for a fair amount for the "assignment problem" / "weighted bipartisan correspondence" and saw variations with different constraints, but did not find what corresponded or what I could reduce to one with this added ordering constraint. Do you have any ideas on how I can solve this? Or maybe rough evidence that it is not solvable in polynomial time (reduction to NP-complete will also work for my purposes)?

Answer 1

This problem has been studied under the name "maximum intersection without intersection". There is a simple quadratic dynamic program. Let M (a, b) be the value of optimal coincidence on n ₁, ..., n _a and m ₁, ..., m <sub> bsub>. We have recurrence

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

argmaxes, .

, -1, , (Khoo and Cong, Fast Multilayer General Area Router MCM Designs).