Geodesic
On the weighted Euclidean matching problem in ${\Bbb R}^d$
Birgit Anthes1 ; Ludger Rüschendorf1
1 Institut für Mathematische Stochastik Universität Freiburg Eckerstr. 1 79104 Freiburg, Germany
Applicationes Mathematicae, Tome 28 (2001) no. 2, pp. 181-190 Cet article a éte moissonné depuis la source Institute of Mathematics Polish Academy of Sciences

Voir la notice de l'article

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.
DOI : 10.4064/am28-2-5
Keywords: partitioning algorithm euclidean matching problem bbb introduced analyzed probabilistic model algorithm uses elements fixed dissection algorithm karp steele zig zag algorithm halton terada traveling salesman problem algorithm runs expected time log p approximates optimal matching probabilistic sense

Birgit Anthes 1 ; Ludger Rüschendorf 1

1 Institut für Mathematische Stochastik Universität Freiburg Eckerstr. 1 79104 Freiburg, Germany 
@article{10_4064_am28_2_5,
     author = {Birgit Anthes and Ludger R\"uschendorf},
     title = {On the weighted {Euclidean
matching} problem in ${\Bbb R}^d$},
     journal = {Applicationes Mathematicae},
     pages = {181--190},
     year = {2001},
     volume = {28},
     number = {2},
     doi = {10.4064/am28-2-5},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4064/am28-2-5/}
}
TY  - JOUR
AU  - Birgit Anthes
AU  - Ludger Rüschendorf
TI  - On the weighted Euclidean
matching problem in ${\Bbb R}^d$
JO  - Applicationes Mathematicae
PY  - 2001
SP  - 181
EP  - 190
VL  - 28
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4064/am28-2-5/
DO  - 10.4064/am28-2-5
LA  - en
ID  - 10_4064_am28_2_5
ER  - 
%0 Journal Article
%A Birgit Anthes
%A Ludger Rüschendorf
%T On the weighted Euclidean
matching problem in ${\Bbb R}^d$
%J Applicationes Mathematicae
%D 2001
%P 181-190
%V 28
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4064/am28-2-5/
%R 10.4064/am28-2-5
%G en
%F 10_4064_am28_2_5
Birgit Anthes; Ludger Rüschendorf. On the weighted Euclidean
matching problem in ${\Bbb R}^d$. Applicationes Mathematicae, Tome 28 (2001) no. 2, pp. 181-190. doi: 10.4064/am28-2-5

Cité par Sources :