JEDNOSTKA NAUKOWA KATEGORII A+

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

Tom 28 / 2001

Birgit Anthes, Ludger Rüschendorf Applicationes Mathematicae 28 (2001), 181-190 MSC: 60F15, 68Q25. DOI: 10.4064/am28-2-5

Streszczenie

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.

Autorzy

  • 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

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek