On the weighted Euclidean matching problem in ℝd
Birgit Anthes ; Ludger Rüschendorf
Applicationes Mathematicae, Tome 28 (2001), p. 181-190 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2001-01-01
EUDML-ID : urn:eudml:doc:279359 
@article{bwmeta1.element.bwnjournal-article-doi-10_4064-am28-2-5,
     author = {Birgit Anthes and Ludger R\"uschendorf},
     title = {On the weighted Euclidean matching problem in $$\mathbb{R}$^d$
            },
     journal = {Applicationes Mathematicae},
     volume = {28},
     year = {2001},
     pages = {181-190},
     zbl = {1052.68055},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-am28-2-5}
}

Birgit Anthes; Ludger Rüschendorf. On the weighted Euclidean matching problem in $ℝ^d$
            . Applicationes Mathematicae, Tome 28 (2001) pp. 181-190. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-am28-2-5/