Approximation algorithms for bipartite and non-bipartite matching in the plane
Kasturi Varadarajan, Pankaj K. Agarwal · 1999
In the approximate Euclidean min-cost perfect matching problem, we are a given a set V of 2n points in the plane, and a real number " ? 0, and we want to pair up the points (into n pairs) so that the sum of the distances between the paired points is within a multiplicative factor of (1 + ") of the optimal. We present a Monte-Carlo algorithm that returns, with probability at least 1=2, a solution within (1 + ") of the optimal; the running time of our algorithm is O((n=" 3 ) log 6 n). In the bipartite version of this problem, we are given a set R of n red points, a set B of n blue points in the plane, and a real number " ? 0. We want to match each red point with a blue point so that the sum of the distances between paired points is within (1 + ") times that of an optimal matching. We present an algorithm for this problem that runs in O((n=") 3=2 log 5 n) time. 1 Introduction In the approximate (Euclidean) min-cost matching problem, we are given a set V of 2n points in the pl...