Loading...
Please wait, while we are loading the content...
Similar Documents
A Near-Linear Constant-Factor Approximation for Euclidean Bipartite Matching? (2004)
| Content Provider | CiteSeerX |
|---|---|
| Author | Agarwal, Pankaj K. |
| Abstract | In the Euclidean bipartite matching problem, we are given a set R of “red ” points and a set B of “blue ” points d in 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. |
| File Format | |
| Publisher Date | 2004-01-01 |
| Access Restriction | Open |
| Subject Keyword | Distinct Blue Point Fixed Constant Euclidean Bipartite Matching Problem Red Point Paired Point Blue Point Euclidean Bipartite Matching Near-linear Constant-factor Approximation Multiplicative Factor |
| Content Type | Text |
