On the Euclidean assignment problem

摘要

The Euclidean assignment problem is a special case of bipartite matching and can be described as follows. For given sets R and B each containing n points in the unit square, find a bijection p: R → B that maximizes (minimizes) the sum of Euclidean distances between pairs of points assigned to each other. We describe a linear time heuristic which solves the maximization case with absolute error of order O(n56) for any problem instance. If R and B are uniformly distributed in the unit square it is further shown that the maximal value z satisfies z/n → (√2 + log(1 + √2))⧸3 almost surely as n → ∞. In this case the heuristic is asymptotically optimal. The approach can also be applied to the minimization case but the results do not seem as promising.