Probabilistic analysis of divide‐and‐conquer heuristics for minimum weighted euclidean matching

The expected costs of the matchings found by various divide‐and‐conquer heuristic algorithms are calculated, under the assumption that the vertices to be matched are uniformly distributed in the unit square. The expected times of the algorithms are calculated as well.