On the weighted Euclidean matching problem in ${ℝ}^d$

Birgit Anthes, and Ludger Rüschendorf. "On the weighted Euclidean matching problem in $ℝ^d$." Applicationes Mathematicae 28.2 (2001): 181-190. <http://eudml.org/doc/279359>.

@article{BirgitAnthes2001,
abstract = {A partitioning algorithm for the Euclidean matching problem in $ℝ^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(logn)^\{p-1\}$ and approximates the optimal matching in the probabilistic sense.},
author = {Birgit Anthes, Ludger Rüschendorf},
journal = {Applicationes Mathematicae},
keywords = {Euclidean matching problem; partitioning algorithm; probabilistic analysis of algorithms},
language = {eng},
number = {2},
pages = {181-190},
title = {On the weighted Euclidean matching problem in $ℝ^d$},
url = {http://eudml.org/doc/279359},
volume = {28},
year = {2001},
}

TY - JOUR
AU - Birgit Anthes
AU - Ludger Rüschendorf
TI - On the weighted Euclidean matching problem in $ℝ^d$
JO - Applicationes Mathematicae
PY - 2001
VL - 28
IS - 2
SP - 181
EP - 190
AB - A partitioning algorithm for the Euclidean matching problem in $ℝ^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(logn)^{p-1}$ and approximates the optimal matching in the probabilistic sense.
LA - eng
KW - Euclidean matching problem; partitioning algorithm; probabilistic analysis of algorithms
UR - http://eudml.org/doc/279359
ER -