Conference proceeding
A near-linear constant-factor approximation for euclidean bipartite matching?
Proceedings of the twentieth annual symposium on computational geometry, pp.247-252
SCG '04
06/08/2004
DOI: 10.1145/997817.997856
Abstract
In the Euclidean bipartite matching problem, we are given a set R of "red" points and a set B of "blue" points in 3 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 ( n 1+ε ) 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.
Details
- Title: Subtitle
- A near-linear constant-factor approximation for euclidean bipartite matching?
- Creators
- Pankaj Agarwal - Duke UniversityKasturi Varadarajan - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the twentieth annual symposium on computational geometry, pp.247-252
- Series
- SCG '04
- DOI
- 10.1145/997817.997856
- Publisher
- ACM
- Language
- English
- Date published
- 06/08/2004
- Academic Unit
- Computer Science
- Record Identifier
- 9984259423802771
Metrics
118 Record Views