# A near-linear constant-factor approximation for euclidean bipartite matching?

Journal Article

In the Euclidean bipartite matching problem, we are given a set R of "red" points and a set B of "blue" points in ℝ d where |R|= |B| = n, and we want to pair up each red point with a distinct blue point so that the sum of distances between the paired points is minimized. We present an approximation algorithm that given any parameter 0 < ε < 1 runs in O(n1+ε) expected time and returns a matching whose expected cost is within a multiplicative factor O(log(1/ε)) of the optimal. The dimension d is considered to be a fixed constant.

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Varadarajan, KR

### Published Date

- January 1, 2004

### Published In

- Proceedings of the Annual Symposium on Computational Geometry

### Start / End Page

- 247 - 252

### Digital Object Identifier (DOI)

- 10.1145/997817.997856

### Citation Source

- Scopus