Optimization from partial solution: minimize sum o

问题:

I have a problem which I like and I love to think about solutions, but I'm stuck unfortunately. I hope you like it too. The problem states:

I have two lists of 2D points(say A and B) and need to pair up points from A with points from B, under the condition that the sum of the distances in all pairs is minimal. A pair contains one point from A and one from B, a point can be used only once, and as many as possible pairs should be created(i.e. min(length(A), length(B))).

I've made a simple example, where color denotes which list the point is from, and the black connections are the solution.

Although this is a nice problem and I suspect is NP-hard, it gets nicer. I can build on existing solutions. Suppose I have two lists and the corresponding solution(i.e. the set of pairs), then the problem I need to solve is to reoptimalize that solution when a point is added to or removed from either list.

I've unfortunately not been able to come up with any non-brute force algorithm yielding the optimal solution. I hope you can. Any algorithm is appreciated in any (pseudo) language, preferably C#.

回答1:

This problem is solvable in polynomial time via the Hungarian algorithm. To get a square matrix, add dummy entries to the shorter list at "distance 0" from everything.

回答2:

Your problem is an instance of the weighted minimum maximal matching problem (as described in this Wikipedia article). There is no polynomial-time algorithm even for the unweighted problem (all distances equal). There are efficient algorithms to approximately solve it in polynomial time (within a factor of 2).

回答3:

This is the minimum weight Euclidean bipartite matching problem. There is a O(n^(2+epsilon)) algorithm.