On the weighted Euclidean matching problem in ${\Bbb R}^d$

Volume 28 / 2001

Birgit Anthes, Ludger Rüschendorf 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.

Authors

  • Birgit AnthesInstitut für Mathematische Stochastik
    Universität Freiburg
    Eckerstr. 1
    79104 Freiburg, Germany
  • Ludger RüschendorfInstitut für Mathematische Stochastik
    Universität Freiburg
    Eckerstr. 1
    79104 Freiburg, Germany
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image