A partitioning algorithm for minimum weighted Euclidean matching (Q794175)

In this paper an example is given of the following heuristics dealing with problems defined on random sets of points distributed uniformly in the Euclidean unit square in the plane: Partition the unit square in a number of smaller subsquares, each containing (on the average) only a small fraction of the points; solve each of these local subproblems, and try to combine these local solutions by some local patching into a global solution for the original instance of the problem. The analysis of the heuristics establishes in a well defined probabilistic model the probability of the event that the result of the heuristics is not much worse than the optimal solution. A classical example where this heuristics has been applied is \textit{R. M. Karp's} application for the Euclidean traveling salesman problem [Math. Oper. Res. 2, 209-224 (1977; Zbl 0391.90091)]. In the present note the heuristics is applied to the problem of finding a minimal weighted Euclidean matching on a set of 2m points selected at random in the unit square. By dividing the square in \(k^ 2\) subsquares with \(k=O(m^{1/2})\) an algorithm is obtained approximating the optimal matching asymptotically with probability 1, such that its running time with high probability is \(O(m^ 3/k^ 2)\). The running time of an algorithm solving the problem exactly is \(O(n^ 3)\).