Vision & Cognition Laboratory

Department of Computer Science, Drexel University

  
home  |  projects  |  people  |  publications  |  facilities  |  sponsors

Optimal Random Matchings on Trees and Applications

In this project 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 $ n$ sets of points $ R = \{r_1,...,r_n\}$ and $ B = \{b_1,...,b_n\}$ distributed uniformly and randomly on the $ m$ leaves of $ l$ -Hierarchically Separated Trees with branching factor $ b$ such that each one of its leaves are of depth $ \delta$ , we will prove that the expected weight of optimal matching between $ R$ and $ B$ is $ \Theta(\sqrt{n\beta}\sum_{k=1}^{\log_b n}(\sqrt{b}l)^k)$ , for $ \beta = 1/b-1/b^2$ . We generalize the upper-bound part for subtrees and for non-uniform distributions. Using low-distortion embedding of $ \mathbb{R}^d$ to HSTs, we reproduce the results concerning the expected optimal transportation cost in $ \lbrack{}0,1\rbrack{}^d$ , except for $ d = 2$ . To address the slightly looser bound for the case of $ d = 2$ , we provide a constant distortion embedding of planar Earth Mover Distance into $ \ell_1$ which in combination with the lower-bound result of Naor and Schechtman on the distortion of embedding of Planar EMD into $ \ell_1$ partly explains the discrepancy by a factor of $ \sqrt{\log n}$ of our result. 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.

Primary Reference
 Jeff Abrahamson. Optimal Matching and Deterministic Sampling Ph.D. Thesis

Related References

Jeff Abrahamson, Bela Csaba, and Ali Shokoufandeh. Optimal Random Matchings on Trees and Applications. Under review for 40th ACM Symposium on Theory of Computing (STOC 2008), May 2008.