RANDOMIZED ALGORITHMS FOR THE ONLINE MINIMUM MATCHING PROBLEM ON EUCLIDEAN-SPACE

Suppose we are given two sets R and B, each of n points in the plane. Define the cost of a matching to be the teal distance of the edges in the, matching. The minimum matching problem on Euclidean space is to f ind a complete bipartite matching which has the minimum cost on Euclid ean space. In this paper, we are interested in the on-line minimum mat ching problem on Euclidean space. We assume the set R is known, but th e points of set B are revealed one by one. When a point of set B arriv es, we must decide what match to make involving the point. None of the matches can be changed after they are made. The on-line minimum match ing problem on Euclidean space tries to minimize the cost of the compl ete bipartite matching that we find. This paper proposes a family of r andomized algorithms, Algorithm RM(m) (1 less than or equal to m less than or equal to n), for solving this problem. When a point in the set B arrived, Algorithm RM(m) randomly chooses at most m unmatched point s in the set R, and adds the minimum edge between the arriving point a nd the chosen points to the matching. In each decision step, the algor ithm only runs in O(m) time, which is superior to the known non-random ized algorithms for this problem. In this paper, we show that Algorith m RM(m) is not a competitive on-line algorithm for 1 less than or equa l to m less than or equal to n-1. However, we further show that if 2n is large, the average cost incurred by Algorithm RM(m) (1 less than or equal to m less than or equal to n) is bounded by O(root n) times the average cost of the optimal Euclidean minimum matching.