PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2001 | 28 | 2 | 181-190
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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.
Słowa kluczowe
Rocznik
Tom
28
Numer
2
Strony
181-190
Opis fizyczny
Daty
wydano
2001
Twórcy
  • Institut für Mathematische Stochastik, Universität Freiburg, Eckerstr. 1, 79104 Freiburg, Germany
  • Institut für Mathematische Stochastik, Universität Freiburg, Eckerstr. 1, 79104 Freiburg, Germany
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_4064-am28-2-5
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.