On the weighted Euclidean matching problem in ${\Bbb R}^d$
Volume 28 / 2001
Applicationes Mathematicae 28 (2001), 181-190
MSC: 60F15, 68Q25.
DOI: 10.4064/am28-2-5
Abstract
A partitioning algorithm for the Euclidean matching problem in ${\Bbb R}^d$ is introduced and analyzed in a probabilistic model. The algorithm uses elements from the fixed dissection algorithm of Karp and Steele (1985) and the Zig-Zag algorithm of Halton and Terada (1982) for the traveling salesman problem. The algorithm runs in expected time $n(\log n)^{p-1}$ and approximates the optimal matching in the probabilistic sense.
