I have 2n random points on a plane. Join pairs of points to make paths. Pair the points such that the summed path length is a minimum. In the picture below, we are trying to minimise the total length of all red-line segments. Points cannot be reused.
Obviously there's the naive brute-force solution, but I wonder if there's a better way. I thought about picking the smallest path then eliminating and picking the next smallest path but then that doesn't guarantee the shortest overall path.