Approximation algorithms for bipartite and non-bipartite matching in the plane

Published

Journal Article

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) log6 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 log5 n) time.

Duke Authors

Cited Authors

  • Varadarajan, KR; Agarwal, PK

Published Date

  • January 1, 1999

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 805 - 814

Citation Source

  • Scopus