How to find the minimum cost of linking two sets of points

Question

I got two sets of points S and V, both have the size n. I want to link the two sets so that every point in S links to one and only one point in V. The cost to link two points is defined as the Euclidean distance between the two points. There should be n! possible ways to link. So how to find the way of minimum cost? (in an efficient way)

Answer 1

This is an assignment problem. You can solve it with the Hungarian Method. There are implementations of this in python. You can also solve the problem with any linear programming solver. The LP formulation will always give you an integer solution.