Name
Abstract | ||
|---|---|---|
In this paper we will consider tight upper and lower bounds on the weight of the optimal matching for random point sets distributed among the leaves of a tree, as a function of its cardinality. Specifically, given two nsets of points R= {r1,...,rn} and B= {b1,...,bn} distributed uniformly and randomly on the mleaves of 茂戮驴-Hierarchically Separated Trees with branching factor bsuch that each of its leaves is at depth 茂戮驴, we will prove that the expected weight of optimal matching between Rand Bis $\Theta(\sqrt{nb}\sum_{k=1}^h(\sqrt{b}\l)^k)$, for h= min (茂戮驴,logbn). Using a simple embedding algorithm from 茂戮驴dto HSTs, we are able to reproduce the results concerning the expected optimal transportation cost in [0,1]d, except for d= 2. We also show that giving random weights to the points does not affect the expected matching weight by more than a constant factor. Finally, we prove upper bounds on several sets for which showing reasonable matching results would previously have been intractable, e.g., the Cantor set, and various fractals. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-85363-3_21 | APPROX-RANDOM |
Keywords | Field | DocType |
constant factor,factor bsuch,reasonable matching result,points r,optimal matching,expected optimal transportation cost,expected weight,optimal random matchings,random weight,upper bound,random point,cantor set,upper and lower bounds | Discrete mathematics,Combinatorics,Transportation cost,Branching factor,Embedding,Optimal matching,Upper and lower bounds,Cantor set,Fractal,Cardinality,Mathematics | Conference |
Volume | ISSN | Citations |
5171 | 0302-9743 | 1 |
PageRank | References | Authors |
0.38 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jeff Abrahamson | 1 | 48 | 6.07 |
| Béla Csaba | 2 | 86 | 8.71 |
| A. Shokoufandeh | 3 | 1356 | 88.63 |