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

• Autorzy: Birgit Anthes , Ludger Rüschendorf
• Języki publikacji: EN

Abstrakty

EN

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.

Kategorie tematyczne

• 60F15: Strong theorems
• 68Q25: Analysis of algorithms and problem complexity

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Applicationes Mathematicae
• Rocznik: 2001
• Tom: 28
• Numer: 2
• Strony: 181-190

Daty

wydano

2001

Twórcy

autor

Birgit Anthes

• Institut für Mathematische Stochastik, Universität Freiburg, Eckerstr. 1, 79104 Freiburg, Germany

autor

Ludger Rüschendorf

• Institut für Mathematische Stochastik, Universität Freiburg, Eckerstr. 1, 79104 Freiburg, Germany

Identyfikatory

DOI

10.4064/am28-2-5